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

Определение:

Производящая функция (англ. generating function) — это формальный степенной ряд: $G(z)=\sum\limits_{n=0}^\infty a_n z^n$, порождающий (производящий) последовательность $(a_0, a_1, a_2, \ldots)$.

Метод производящих функций был разработан Эйлером в 1750-х годах.

Применение

Производящая функция используется для:

• Компактной записи информации о последовательности.
• Нахождения зависимости $a_n(n)$ для последовательности $a_n$, заданной рекуррентным соотношением. Например, для чисел Фибоначчи.
• Нахождения рекуррентного соотношения для последовательности — вид производящей функции может помочь найти формулу.
• Исследования асимптотического поведения последовательности.
• Доказательства тождеств с последовательностями.
• Решения задачи подсчета объектов в комбинаторике. Например, в доказательстве пентагональной теоремы или в задаче нахождения количества расстановок $m$ ладей на доске $n \times n$.
• Вычисления бесконечных сумм.

Примеры производящих функций

Рассмотрим производящие функции для различных комбинаторных последовательностей:

• $\prod\limits_{ n = 1}^\infty(1-x^n)$ — производящая функция для разности количества разбиений числа $n$ в четное и нечетное число различных слагаемых. Например, коэффициент при $x^5$ равен $+1$, потому что существует два разбиения на четное число различных слагаемых $(4+1; 3+2)$ и одно на нечетное ($5$). Правильность этого легко осознать, если понять, что каждая скобка представляет какое-то слагаемое и мы можем его взять (второе слагаемое — $-x^k$) или не взять (первое — $1$). Эта производящая функция используется в комбинаторном доказательстве пентагональной теоремы.

• $\prod\limits_{n=1}^\infty \dfrac{1}{1-x^n}$ — производящая функция для последовательности $p_n$, где $p_i$ — число разбиений числа $i$ на слагаемые.

• $\prod\limits_{ n = 1}^\infty(1+x^n)$ — производящая функция для последовательности $d_n$, где $d_i$ — число разбиений на различные слагаемые.

• $\prod\limits_{n=1}^\infty(1+x^{ 2n - 1})$ — производящая функция для последовательности $l_n$, где $l_i$ — число разбиений на нечётные слагаемые. С помощью метода производящих функций можно доказать, что производящие функции последовательностей равны, соответственно $d_n = l_n$: $\prod\limits_{n=1}^\infty(1+x^{ n})=\prod\limits_{n=1}^\infty \dfrac{1-x^{2n}}{1-x^n}=\dfrac{1-x^2}{1-x}\dfrac{1-x^4}{1-x^2}\dfrac{1-x^6}{1-x^3}\ldots=$

$=\dfrac{1}{1-x}\dfrac{1}{1-x^3}\dfrac{1}{1-x^5}\ldots=\prod\limits_{n=1}^\infty(1+x^{ 2n - 1})$

Примеры решений задач методом производящих функций

Решение рекуррентных соотношений

Существует целый класс последовательностей, задаваемых рекуррентным соотношением, например, $f_n$ — числа Фибоначчи или $C_n$ — числа Каталана. Метод производящих функций позволяет получить выражение для $a_n$ через номер элемента в последовательности в замкнутом виде, то есть в таком виде, что выражение можно вычислить, предполагая, что $z$ достаточно мало.

Пусть последовательность $(a_0, a_1, a_2, \ldots)$ удовлетворяет некоторому рекуррентному соотношению. Мы хотим получить выражение для $a_n$ (при $n \geqslant 0$) в замкнутом виде. Алгоритм получения замкнутого выражения для чисел $a_n$, удовлетворяющих рекуррентному соотношению, с помощью производящих функций состоит из 4 шагов:

1. Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен $k$, то есть количество предшествующих элементов, требуемых для вычисления элемента с номером $n$, равно $k$):

   $a_0=\ldots,$

   $a_1=\ldots,$

   $\ldots$

   $a_{k-1}=\ldots,$

   $a_{n}=\ldots, n \geqslant k.$

2. Домножить каждую строчку на $z$ в соответствующей степени и просуммировать строчки для всех $n \geqslant 0$.
3. В полученном уравнении привести все суммы к замкнутому виду. Получить уравнение для производящей функции.
4. Выразить $G(z)$ в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням $z$.

Для демонстрации универсальности метода рассмотрим довольно произвольное рекуррентное соотношение:

$a_0= 1,$

$a_1= 2,$

$a_n= 6a_{ n - 1}-8a_{n-2}+n, n \geqslant 2$

Запишем производящую функцию для этой последовательности и преобразуем правую часть:

$G(z)=a_0+a_1z+\sum\limits_{n=2}^\infty(6a_{ n - 1}-8a_{n-2}+n) z^n$

$G(z)=a_0+a_1z+6\sum\limits_{n=2}^\infty a_ { n-1} z^n - 8\sum\limits_{n=2}^\infty a_ { n-2} z^n+\sum\limits_{n=2}^\infty n z^n$

$G(z)=a_0+a_1z+6z\sum\limits_{n=1}^\infty a_ { n } z^n - 8z^2\sum\limits_{n=0}^\infty a_ { n } z^n+\sum\limits_{n=2}^\infty n z^n$

$G(z)=a_0+a_1z+6z(G(z)-a_0) - 8z^2G(z)+\sum\limits_{n=2}^\infty n z^n$

$G(z)=1-4z+6zG(z) - 8z^2G(z)+\sum\limits_{n=2}^\infty n z^n$

Для того, чтобы замкнуть последнюю сумму воспользуемся очень важным приемом, который используется при преобразовании производящих функций. Фактически мы имеем дело с последовательностью $nb_n$ (в нашем случае последовательность $b_n= (1, 1, 1, \ldots)$). Такая последовательность получается путём дифференцирования функции $B(z)$, производящей для $b_n$, с последующим умножением результата на $z$:

$zB'(z)=z(\sum\limits_{n=0}^\infty b_n z^n)'=z\sum\limits_{ n = 1}^\infty nb_n z^{n-1}=\sum\limits_{n=0}^\infty nb_n z^n$

Тогда замкнем последнее слагаемое следующим образом:

$\sum\limits_{n=2}^\infty n z^n=z \sum\limits_{n=2}^\infty n z^{n-1}= z(\sum\limits_{ n = 2}^\infty z^n)'$

$\sum\limits_{n=2}^\infty z^n=\sum\limits_{n=0}^\infty z^n-1-z=\dfrac{1}{1-z}-1-z=\dfrac{z^2}{1-z}$

$z(\dfrac{ z ^ 2}{1-z})'=\dfrac{z^2(2-z)}{(1-z)^2}$

Таким образом, наше последнее слагаемое примет вид:

$G(z)=1-4z+6zG(z) - 8z^2G(z)+\dfrac{z^2(2-z)}{(1-z)^2}$

Это уравнение для производящей функции. Из него выражаем $G(z)$:

$G(z)=\dfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}$

Разложим знаменатель на множители и разобьём дробь на сумму простых дробей :

$G(z) =\dfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}=\dfrac{1-6z+11z^2-5z^3}{(1-2z)(1-4z)(1-z)^2}=\dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}$

Разложим первое слагаемое в ряд, используя расширенные биномиальные коэффициенты :

$\dfrac{ 1}{(1-z)^2}=(1-z)^{-2}=\sum\limits_{n=0}^{\infty} {-2\choose n}(-z)^n=\sum\limits_{n=0}^{\infty} (-1)^n{n+1\choose 1}(-z)^n=\sum\limits_{n=0}^{\infty}(n+1)z^n$

$G(z)=\dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}=\dfrac{1}{3}\sum\limits_{n=0}^{\infty} (n+1)z^n +\dfrac{7}{9}\sum\limits_{n=0}^{\infty} z^n - \dfrac{1}{2}\sum\limits_{n=0}^{\infty} 2^n z^n + \dfrac{7}{18}\sum\limits_{n=0}^{\infty} 4^n z^n$

$a_n=\dfrac{n+1}{3}+\dfrac{7}{9}-\dfrac{2^n}{2}+\dfrac{7 \cdot 4^n}{18}=\dfrac{7 \cdot 4^n+6n+20}{18}-2^{n-1}$

Расчет дисперсии геометрического распределения

Метод производящих функций также используется для нахождения математического ожидания и дисперсии различных распределений в теории вероятностей. Например, в геометрическом распределении для нахождения дисперсии $\operatorname{D}(\xi)=\operatorname{E}(\xi^2)-(\operatorname{E}(\xi))^2$ нужно найти два мат. ожидания:

• $\operatorname{E}(\xi)=\sum\limits_{n=1}^{\infty}n p(1-p)^{n-1}$

• $\operatorname{E}(\xi^2) = \sum\limits_{n=1}^{\infty}n^{2}p(1-p)^{n-1}$

которые фактически являются производящими функциями последовательностей $1, 2, 3\ldots$ и $1, 4, 9\ldots$:

• $\operatorname{ E}(\xi)=\sum\limits_{n=1}^{\infty}n p(1-p)^{n-1} =$

$= \sum\limits_{n=0}^{\infty}(n+1) p(1-p)^{n} =$

$= \sum\limits_{n=0}^{\infty}n p(1-p)^{n} + \sum\limits_{n=1}^{\infty} p(1-p)^{n-1} =$

$= (1-p) \operatorname{E}(\xi) +1 \Rightarrow \operatorname{E}(\xi) = \dfrac{1}{p}$

• $\operatorname{E}(\xi^2) = p\sum\limits_{n=1}^{\infty}n^{2}(1-p)^{n-1} =$

$=p\sum\limits_{n=1}^{\infty}n(n+1)(1-p)^{n-1} - p\sum\limits_{n=1}^{\infty}n(1-p)^{n-1} =$

$= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\sum\limits_{n=1}^{\infty}(1-p)^{n+1} + p\dfrac{\operatorname{d}}{\operatorname{d}p}\sum\limits_{n=1}^{\infty}(1-p)^{n} =$

$= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\sum\limits_{ n = 0}^{\infty}(1-p)^{n} \cdot(1-p)^2\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\sum\limits_{ n = 0}^{\infty}(1-p)^{n}\cdot(1-p)\right) =$

$= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\dfrac{ 1}{1-(1-p)} \cdot(1-p)^2\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\dfrac{ 1}{1-(1-p)}\cdot(1-p)\right) =$

$= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\dfrac{ (1 - p) ^ 2}{p}\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\dfrac{ 1 - p}{p}\right) =$

$= p\cdot\dfrac{2}{p^3} - p\cdot\dfrac{1}{p^2} = \dfrac{2}{p^{2}} - \dfrac{1}{p} = \dfrac{2-p}{p^{2}}$.

Тогда:

$\operatorname{D}(\xi)=\operatorname{E}(\xi^2)-(\operatorname{E}(\xi))^2= \dfrac{2-p}{p^{2}}-\dfrac{1}{p^2}=\dfrac{1-p}{p^2}$

Пример задачи на нахождение производящей функции

Задача:

Рассмотрим множество путей на прямой, состоящих из шагов длины $1$ вправо и влево. Найдите производящую функцию для числа таких путей из $n$ шагов, начинающихся в $0$ и оканчивающихся в $0$.

Заметим, что для того, чтобы закончить путь в $0$, необходимо совершить равное число шагов вправо и влево. Тогда задача сводится к тому, чтобы выбрать $\dfrac{n}{2}$ позиций для, например, шагов вправо из всего $n$ шагов. Тогда ответом будет сумма от нуля до бесконечности по $n$ всех $C^{n}_{2n}$. То есть: $g(x) = \sum\limits_{0}^{\infty} C^{n}_{2n} x^n$ Рассмотрим $f(x) = \sum\limits_{0}^{\infty} C_n x^n$, где $C_n$ — число Каталана. Тогда, заметим что $f'(x) = \sum\limits_{0}^{\infty} n C_n x^{n-1}$. Так как $C_n = \dfrac{1}{n+1} C_{2n}^n$, то справедливо равенство: $g(x) = (n+1)f(x) = xf'(x) + f(x)$

Мы знаем, что производящая функция для чисел Каталана равна $f(x) = \dfrac{1-\sqrt{1-4x}}{2x}$. Найдем $f'(x)$.

$f'(x) = \dfrac{\dfrac{4x}{\sqrt{1-4x}} - 2 + 2\sqrt{1-4x}}{4x^2} = \dfrac{1 - 2x - \sqrt{1-4x}}{2x^2 \sqrt{1-4x}}$

Соответственно, ответом будет производящая функция вида:

$g(x) = \dfrac{1 - 2x - \sqrt{1-4x}}{2x \sqrt{1-4x}} + \dfrac{1-\sqrt{1-4x}}{2x}$

Задача:

Рассмотрим множество путей на прямой, состоящих из шагов длины $1$ вправо и влево. Найдите производящую функцию для числа таких путей из $n$ шагов, начинающихся и оканчивающихся в $0$ и не заходящих в отрицательную полупрямую.

Заметим, что задача аналогична Правильной скобочной последовательности. Тогда производящей функцией для нашей задачи будет производящая функция для правильной скобочной последовательности, а именно:

$g(x) = \dfrac{1-\sqrt{1-4x}}{2x}$

Приложения

Примеры простых производящих функций

На последнем шаге приведения производящей функции к замкнутому виду требуется разложить полученные слагаемые в ряд. Для этого можно воспользоваться таблицей основных производящих функций .

Все суммы выполняются по переменной $n$ от $0$ до $\infty$. Элементы последовательности нумеруются от $0$.

Последовательность	Производящая функция в виде ряда	Производящая функция в замкнутом виде
$(1, 0, 0,\ldots)$	$1$	$1$
$(0, 0, \ldots, 0, 1, 0, 0\ldots)$ ($m$ нулей в начале)	$z^m$	$z^m$
$(1, 1, 1,\ldots)$	$\sum\limits z^n$	$\dfrac{1}{1-z}$
$(1, 0, 0, \ldots, 0, 1, 0, 0, \ldots 0, 1, 0, 0\ldots)$ (повторяется через $m$)	$\sum\limits z^{nm}$	$\dfrac{1}{1-z^m}$
$(1, -1, 1, -1,\ldots)$	$\sum\limits (-1)^nz^n$	$\dfrac{1}{1+z}$
$(1, 2, 3, 4,\ldots)$	$\sum\limits (n+1)z^n$	$\dfrac{1}{(1-z)^2}$
$(1, 2, 4, 8, 16,\ldots)$	$\sum\limits 2^nz^n$	$\dfrac{1}{(1-2z)}$
$(1, r, r^2, r^3,\ldots)$	$\sum\limits r^nz^n$	$\dfrac{1}{(1-rz)}$
$($${m\choose 0}, {m\choose 1}, {m\choose 2}, {m\choose 3},\ldots$$)$	$\sum\limits {m\choose n}$ $z^n$	$(1+z)^m$
$($$1, {{m}\choose m}, {{m+1}\choose m}, {{m+2}\choose m},\ldots$$)$	$\sum\limits {{m+n-1}\choose n}$ $z^n$	$\dfrac{1}{(1-z)^m}$
$($$1, {{m+1}\choose m}, {{m+2}\choose m}, {{m+3}\choose m},\ldots$$)$	$\sum\limits {{m+n}\choose n}$ $z^n$	$\dfrac{1}{(1-z)^{m+1}}$
$(0, 1, -\dfrac{1}{2}, \dfrac{1}{3}, -\dfrac{1}{4},\ldots)$	$\sum\limits \dfrac{(-1)^{n+1}}{n}$ $z^n$	$\ln(1+z)$
$(1, 1, \dfrac{1}{2}, \dfrac{1}{6}, \dfrac{1}{24},\ldots)$	$\sum\limits \dfrac{1}{n!}$ $z^n$	$e^z$
$(1, -\dfrac{1}{2!}m^2, \dfrac{1}{4!}m^4, -\dfrac{1}{6!}m^6, \dfrac{1}{8!}m^8,\ldots)$	$\sum\limits \dfrac{1}{(2n)!}$ $m^{(2n)}$	$\cos m$
$(m, -\dfrac{1}{3!}m^3, \dfrac{1}{5!}m^5, -\dfrac{1}{7!}m^7, \dfrac{1}{9!}m^9,\ldots)$	$\sum\limits \dfrac{1}{(2n-1)!}$ $m^{(2n-1)}$	$\sin m$

См. также

• Производящая функция Дирихле

Источники информации

• Вайнштейн Ф., Разбиение чисел. Журнал "Квант" № 11, 1988 год
• Производящие функции
• Wikipedia — Generating function
• Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера
• Graham, Knuth, and Patashnik: Concrete Mathematics