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

Как найти замкнутую формулу для n-го числа Фибоначчи без рекурсии? Почему количество правильных скобочных последовательностей и количество BST описываются одной формулой? Производящие функции превращают рекуррентные соотношения в алгебраические уравнения - и дают ответы, которые иначе найти очень сложно.

• **Анализ алгоритмов:** OGF чисел Каталана объясняет, почему наивная рекурсия для задач на BST/скобки - O(4ⁿ/n^{3/2}), а динамическое программирование - O(n²)
• **Криптография:** OGF для разбиений числа на простые слагаемые связана с функцией Эйлера и используется в анализе информационной безопасности схем
• **Компиляторы:** подсчёт числа деревьев разбора для грамматик - именно задача для OGF

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

• Основы комбинаторики

Обыкновенная производящая функция (OGF): последовательность как многочлен

Производящая функция - это «кодировщик» последовательности. Вместо того чтобы хранить числа a₀, a₁, a₂, ... как список, мы записываем их как коэффициенты формального степенного ряда: A(x) = a₀ + a₁x + a₂x² + a₃x³ + .... Это позволяет использовать алгебру многочленов для решения комбинаторных задач.

**Обыкновенная производящая функция (OGF)** последовательности (a₀, a₁, a₂, ...) - это формальный степенной ряд: A(x) = Σ aₙ · xⁿ = a₀ + a₁x + a₂x² + a₃x³ + ... x - формальная переменная, не число! Нас интересуют коэффициенты, а не значения ряда.

Ключевое свойство: **коэффициент при xⁿ в A(x)** - это именно aₙ. Обозначают [xⁿ]A(x) = aₙ. Чтобы найти n-й член последовательности, достаточно разложить замкнутую форму A(x) в степенной ряд и взять коэффициент при xⁿ.

**Почему это работает для CS-инженера:** замкнутые формы OGF превращают рекуррентные формулы (которые вычисляются за O(n)) в аналитические выражения. Из OGF можно извлечь асимптотику, доказать тождества и находить коэффициенты без рекурсии.

Операции над OGF: сложение, умножение, свёртка

Главная сила производящих функций - в том, что алгебраические операции над ними соответствуют осмысленным комбинаторным операциям над последовательностями. Сложение OGF - объединение, умножение - свёртка (convolution), что соответствует подсчёту разбиений.

**Основные операции:** • **Сложение:** A(x) + B(x) соответствует (aₙ + bₙ) • **Умножение (свёртка):** A(x)·B(x) соответствует (Σₖ aₖ·bₙ₋ₖ) - число способов разбить n на два слагаемых • **Сдвиг:** xᵏ·A(x) сдвигает последовательность на k позиций вправо • **Производная:** A'(x) = Σ n·aₙ·xⁿ⁻¹ - коэффициенты умножаются на их индекс

**Формальный ряд vs. сходимость:** x в OGF - формальная переменная, а не число. Мы не подставляем значения x и не говорим о сходимости ряда. OGF - это алгебраический инструмент для работы с коэффициентами, а не аналитическая функция.

Решение рекуррентностей через OGF

Производящие функции - мощный инструмент для решения рекуррентных соотношений. Идея: записать OGF A(x) = Σ aₙxⁿ, умножить рекуррентное уравнение на xⁿ и просуммировать по всем n ≥ 0. Получаем алгебраическое уравнение для A(x), из которого находим замкнутую форму, затем извлекаем коэффициенты.

**Алгоритм решения рекуррентности через OGF:** 1. Записать OGF: A(x) = Σ aₙxⁿ 2. Умножить рекуррентность aₙ = f(aₙ₋₁, aₙ₋₂, ...) на xⁿ, суммировать 3. Выразить суммы через A(x) (используя сдвиги: Σ aₙ₋₁xⁿ = x·A(x)) 4. Решить уравнение для A(x) 5. Разложить A(x) в частичные дроби и в степенной ряд → aₙ

**OGF vs. EGF (экспоненциальная производящая функция):** OGF A(x) = Σ aₙxⁿ используется для задач с неупорядоченными объектами. EGF Â(x) = Σ aₙxⁿ/n! - для упорядоченных объектов (перестановок). Числа Фибоначчи и разбиения - OGF; количество помеченных деревьев и перестановок с заданными свойствами - EGF.

Числа Каталана: OGF для корневых структур

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

**Числа Каталана:** C₀=1, C₁=1, C₂=2, C₃=5, C₄=14, C₅=42, ... Рекуррентность: Cₙ = Σₖ₌₀ⁿ⁻¹ Cₖ·Cₙ₋₁₋ₖ (свёртка!) OGF: C(x) = Σ Cₙxⁿ удовлетворяет уравнению: C(x) = 1 + x·C(x)² Замкнутая форма: C(x) = (1 − √(1−4x)) / (2x) Замкнутая формула: Cₙ = C(2n,n)/(n+1)

Рекуррентность Cₙ = Σ Cₖ·Cₙ₋₁₋ₖ - это свёртка, которая в терминах OGF записывается как C(x) = 1 + x·C(x)². Решая квадратное уравнение, получаем C(x) = (1 − √(1−4x)) / (2x). Это и есть замкнутая OGF - из неё биномиальным рядом извлекается формула Cₙ = C(2n,n)/(n+1).

**Практическое значение:** числа Каталана - граница наивного DP. Если задача сводится к «посчитать число BST / скобочных структур / триангуляций», замкнутая формула заменяет O(n²) DP. Знание OGF объясняет, откуда эта формула берётся.

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

• **OGF** A(x) = Σ aₙxⁿ кодирует последовательность (a₀, a₁, ...) как формальный степенной ряд. Коэффициент [xⁿ]A(x) = aₙ.
• **Умножение OGF - это свёртка** последовательностей: [xⁿ](A·B) = Σ aₖ·bₙ₋ₖ. Применяется для подсчёта разбиений.
• **Рекуррентности через OGF:** умножаем рекуррентность на xⁿ, суммируем, выражаем через A(x), решаем уравнение → замкнутая форма.
• **Числа Каталана** Cₙ = C(2n,n)/(n+1) - OGF удовлетворяет C(x) = 1 + x·C(x)². Считают BST, скобочные структуры, триангуляции.

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

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

• Комбинаторика: основы — Биномиальные коэффициенты C(n,k) - коэффициенты в разложении (1+x)ⁿ, OGF для сочетаний
• Принцип включений-исключений — PIE можно выводить через OGF: знакочередующиеся суммы возникают из формальных обратных произведений
• Теория графов — Подсчёт деревьев (формула Кэли: nⁿ⁻²) выводится через EGF и логарифмы производящих функций

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

• Как OGF для задачи о количестве способов раздать сдачу монетами {1, 5, 10} связана с задачей о разбиении числа на части?
• Почему числа Каталана появляются и в задаче о BST, и в задаче о скобочных последовательностях? Какая общая структура за ними стоит?
• Как бы вы использовали OGF для подсчёта числа бинарных строк длины n без двух подряд идущих нулей?

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

• prob-02-combinatorics