🔀 Дискретка

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

Q: Что метод даёт по сравнению с голой рекуррентностью?

Рекуррентность отвечает на вопрос «как получить следующий член», производящая функция — «что это за объект целиком». Из неё выходят замкнутая формула (как $C_n = \binom{2n}{n}/(n+1)$), асимптотика по поведению около особых точек и связи между разными последовательностями через операции над рядами.

англ. Generating function

Степенной ряд $G(s) = \sum a_k s^k$, упаковывающий последовательность в коэффициенты: свёртки превращаются в умножение рядов, рекуррентности — в алгебраические уравнения, и ответ вынимается как коэффициент.

Производящая функция последовательности $(a_{0}, a_{1}, a_{2}, \dots)$ — степенной ряд $G (s) = \sum_{k \geq 0} a_{k} s^{k}$ , в котором последовательность спрятана в коэффициенты. Это кодировка, а не функция для построения графика: переменная $s$ держит место, сами значения $G$ часто не нужны. Достоинство приёма в том, что операции над последовательностями становятся операциями над рядами: сдвиг — умножение на $s$ , свёртка — произведение, рекуррентность — алгебраическое уравнение. В комбинаторике так считают: $a_{k}$ — число объектов размера $k$ , и разбор объекта на части превращается в умножение рядов.

Главная операция — произведение по Коши. Если $G$ кодирует выбор первой части объекта, а $H$ — второй, то коэффициент при $s^{n}$ в произведении равен $\sum_{k} a_{k} b_{n - k}$ : перебраны все способы разделить размер $n$ между частями. Именно свёртка — точный образ комбинаторного правила «сначала то, потом это». Вопрос сходимости на первом этапе можно честно игнорировать: формальные степенные ряды складываются и умножаются по школьным правилам, пока мы не захотели подставлять числа и считать пределы.

G (s) \cdot H (s) = n \geq 0 \sum (k = 0 \sum n a_{k} b_{n - k}) s^{n}

произведение производящих функций — свёртка коэффициентов; комбинаторно: собрать объект размера

n

из куска типа

A

и куска типа

B

Классический пример — числа Каталана $1, 1, 2, 5, 14, 42$ : количество правильных скобочных последовательностей из $n$ пар. Они удовлетворяют рекуррентности $C_{n + 1} = \sum_{k = 0}^{n} C_{k} C_{n - k}$ — объект распадается на две меньшие скобочные структуры. В языке производящих функций это уравнение $G = 1 + s G^{2}$ , то есть $s G^{2} - G + 1 = 0$ . Решаем квадратное уравнение и берём ветвь с минусом — только она конечна при $s = 0$ : $G (s) = \frac{1 - 1 - 4 s}{2 s}$ . Биномиальное разложение даёт $1 - 4 s = 1 - 2 s - 2 s^{2} - 4 s^{3} - 10 s^{4} - 28 s^{5} - \dots$ , делим на $2 s$ : $G (s) = 1 + s + 2 s^{2} + 5 s^{3} + 14 s^{4} + 42 s^{5}$ — коэффициенты совпали с Каталанами, а попутно вынимается явная формула $C_{n} = \frac{1}{n + 1} (n 2 n)$ . Для Фибоначчи $1, 1, 2, 3, 5, 8$ та же техника проще: рекуррентность даёт $G = \frac{1}{1 - s - s ^{2}}$ .

Техника в теме — урок рекуррентные соотношения; аналитическая сторона степенных рядов — урок степенные ряды. Словарь: числа Фибоначчи — модельный пример, ряд — базовое понятие, математическая индукция — способ проверить вынутую формулу. Потренировать счёт вариантов — тренажёр по комбинаторике; формулы — в шпаргалке.

Частые вопросы

Нужна ли сходимость ряда?

Для комбинаторных применений — нет: работают формальные степенные ряды, где $s$ лишь помечает позицию коэффициента, а сложение и умножение чисто алгебраические. Сходимость становится важной, когда хочется подставлять числа: например, ряд Каталана сходится при $∣ s ∣ < 1/4$ , и в граничной точке живут оценки роста коэффициентов.

Что метод даёт по сравнению с голой рекуррентностью?

Рекуррентность отвечает на вопрос «как получить следующий член», производящая функция — «что это за объект целиком». Из неё выходят замкнутая формула (как $C_{n} = (n 2 n) / (n + 1)$ ), асимптотика по поведению около особых точек и связи между разными последовательностями через операции над рядами.