Производящие функции

Рекуррентность Фибоначчи выглядит страшно, но производящая функция превращает её в простое алгебраическое уравнение - и даёт явную формулу. Это не магия, это кодирование последовательностей в алгебраические объекты.

• **Задача о размене монет (DP):** OGF P(x) - это ровно та же структура, что таблица DP для задачи о разбиении, алгоритм за O(n·√n)
• **Анализ алгоритмов:** производящие функции решают рекуррентности T(n) = T(n/2) + f(n) в явном виде без мастер-теоремы
• **Компиляторы и парсеры:** число корректных синтаксических деревьев для грамматики считается через OGF, связанную с числами Каталана

Предварительные знания

• Probabilistic Combinatorics

Обыкновенные производящие функции (OGF)

Обыкновенная производящая функция (OGF) последовательности (a₀, a₁, a₂, ...) - это формальный степенной ряд A(x) = ∑ aₙ xⁿ. Слово «формальный» означает: нас не интересует сходимость, только алгебраические операции над рядами. Сложение, умножение, взятие обратного - всё это операции над последовательностями.

**Рекуррентности через OGF:** если aₙ = aₙ₋₁ + aₙ₋₂ (Фибоначчи), то A(x) = x/(1-x-x²). Разложив на простые дроби, получаем явную формулу через φⁿ/√5 (формула Бине) - без угадывания.

Экспоненциальные производящие функции (EGF)

Экспоненциальная производящая функция (EGF) последовательности (a₀, a₁, a₂, ...) - это A(x) = ∑ aₙ xⁿ/n!. EGF удобна для перечисления упорядоченных структур (перестановок, слов). Произведение EGF соответствует «помеченному» объединению структур.

**EGF vs OGF:** используйте OGF для неупорядоченных структур (подмножества, мультимножества) и EGF для упорядоченных (перестановки, слова, деревья с корнем). EGF перемножаются, когда нужно «расставить метки» по объединённой структуре.

Числа Каталана и их OGF

Числа Каталана Cₙ = C(2n,n)/(n+1) - одни из самых «универсальных» в комбинаторике. Они считают: корректные скобочные последовательности длины 2n, бинарные деревья с n+1 листьями, триангуляции (n+2)-угольника, пути Дика длины 2n и ещё более 200 комбинаторных интерпретаций.

**Трюк с OGF:** уравнение C(x) = 1 + x·C(x)² получается из рекуррентности автоматически. Такие «самоссылающиеся» уравнения на OGF типичны для рекурсивных структур (деревья, скобки). Извлечение коэффициентов - через формулу Лагранжа.

Разбиения числа и теорема Эйлера

Функция разбиения p(n) считает число представлений n в виде суммы натуральных чисел (порядок не важен): p(4) = 5 (4, 3+1, 2+2, 2+1+1, 1+1+1+1). OGF функции разбиения - бесконечное произведение Эйлера: ∏_{k=1}^{∞} 1/(1-xᵏ).

**Связь с информатикой:** задача о разбиении числа - классическая задача динамического программирования (задача о размене монет). OGF P(x) объясняет алгоритм DP: каждый множитель 1/(1-xᵏ) соответствует «монете» достоинства k.

Ключевые идеи

• **OGF** A(x) = ∑aₙxⁿ: умножение = свёртка; используется для неупорядоченных структур
• **EGF** A(x) = ∑aₙxⁿ/n!: умножение = помеченное объединение; используется для перестановок
• **Числа Каталана** Cₙ = C(2n,n)/(n+1): OGF удовлетворяет C = 1 + x·C², более 200 комбинаторных интерпретаций
• **Разбиения числа:** P(x) = ∏1/(1-xᵏ), рекуррентность через пентагональные числа, асимптотика ∼ e^{π√(2n/3)}

Связанные темы

Производящие функции связывают комбинаторику с алгебраическими методами:

• Числа Стирлинга и Белла — EGF чисел Белла и Стирлинга выражаются через e^{e^x - 1} и (e^x - 1)^k/k! соответственно
• Перечислительная комбинаторика в анализе алгоритмов — Производящие функции решают рекуррентности T(n) - основной инструмент точного анализа алгоритмов

Вопросы для размышления

• Почему для рекурсивных структур (деревья, скобки) уравнение на OGF получается «само собой» из структурного определения?
• Как связаны OGF задачи о разбиении числа и алгоритм динамического программирования для задачи о размене монет?
• Что означает произведение двух EGF в комбинаторном смысле - какую операцию над структурами оно описывает?

Связанные уроки

• calc-02-series-intro