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

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

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

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

Применение

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

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

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

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

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

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

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

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

[math] \prod_{n=1}^\infty (1+x^{n})=\prod_{n=1}^\infty \frac{1-x^{2n}}{1-x^n}=\frac{1-x^2}{1-x}\frac{1-x^4}{1-x^2}\frac{1-x^6}{1-x^3}...=[/math]

[math]=\frac{1}{1-x}\frac{1}{1-x^3}\frac{1}{1-x^5}...=\prod_{n=1}^\infty (1+x^{2n-1})[/math]

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

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

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

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

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

   [math]a_0=...,[/math]

   [math]a_1=...,[/math]

   [math]a_{k-1}=...,[/math]

   [math]a_{n}=..., n \ge k.[/math]

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

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

[math]a_0=1,[/math]

[math]a_1=2,[/math]

[math]a_n=6a_{n-1}-8a_{n-2}+n, n \ge 2[/math]

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

[math]G(z)=a_0+a_1z+\sum_{n=2}^\infty (6a_{n-1}-8a_{n-2}+n) z^n[/math]

[math]G(z)=a_0+a_1z+6\sum_{n=2}^\infty a_{n-1}z^n - 8\sum_{n=2}^\infty a_{n-2}z^n+\sum_{n=2}^\infty n z^n[/math]

[math]G(z)=a_0+a_1z+6z\sum_{n=1}^\infty a_{n}z^n - 8z^2\sum_{n=0}^\infty a_{n}z^n+\sum_{n=2}^\infty n z^n[/math]

[math]G(z)=a_0+a_1z+6z(G(z)-a_0) - 8z^2G(z)+\sum_{n=2}^\infty n z^n[/math]

[math]G(z)=1-4z+6zG(z) - 8z^2G(z)+\sum_{n=2}^\infty n z^n[/math]

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

[math]zB'(z)=z(\sum_{n=0}^\infty b_n z^n)'=z\sum_{n=1}^\infty nb_n z^{n-1}=\sum_{n=0}^\infty nb_n z^n[/math]

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

[math]\sum_{n=2}^\infty n z^n=z \sum_{n=2}^\infty n z^{n-1}= z (\sum_{n=2}^\infty z^n)'[/math]

[math]\sum_{n=2}^\infty z^n=\sum_{n=0}^\infty z^n-1-z=\frac{1}{1-z}-1-z=\frac{z^2}{1-z}[/math]

[math]z (\frac{z^2}{1-z})'=\frac{z^2(2-z)}{(1-z)^2}[/math]

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

[math]G(z)=1-4z+6zG(z) - 8z^2G(z)+\frac{z^2(2-z)}{(1-z)^2}[/math]

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

[math]G(z)=\frac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}[/math]

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

[math]G(z)=\frac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}=\frac{1-6z+11z^2-5z^3}{(1-2z)(1-4z)(1-z)^2}=\frac{1/3}{(1-z)^2}+\frac{7/9}{1-z}-\frac{1/2}{1-2z}+\frac{7/18}{1-4z}[/math]

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

[math]\frac{1}{(1-z)^2}=(1-z)^{-2}=\sum_{n=0}^{\infty} {-2\choose n}(-z)^n=[/math]

[math]=\sum_{n=0}^{\infty} (-1)^n{n+1\choose 1}(-z)^n=\sum_{n=0}^{\infty}(n+1)z^n[/math]

[math]G(z)=\frac{1/3}{(1-z)^2}+\frac{7/9}{1-z}-\frac{1/2}{1-2z}+\frac{7/18}{1-4z}=[/math]

[math]=\frac{1}{3}\sum_{n=0}^{\infty} (n+1)z^n +\frac{7}{9}\sum_{n=0}^{\infty} z^n - \frac{1}{2}\sum_{n=0}^{\infty} 2^n z^n + \frac{7}{18}\sum_{n=0}^{\infty} 4^n z^n[/math]

[math]a_n=\frac{n+1}{3}+\frac{7}{9}-\frac{2^n}{2}+\frac{7 \cdot 4^n}{18}=\frac{7 \cdot 4^n+6n+20}{18}-2^{n-1}[/math]

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

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

• [math]\operatorname{E}(\xi)=\sum_{n=1}^{\infty}n p (1-p)^{n-1} [/math]

• [math] \operatorname{E}(\xi^2) = \sum_{n=1}^{\infty}n^{2}p(1-p)^{n-1}[/math]

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

• [math]\operatorname{E}(\xi)=\sum_{n=1}^{\infty}n p (1-p)^{n-1} = [/math]

[math]= \sum_{n=0}^{\infty}(n+1) p (1-p)^{n} = [/math]

[math]= \sum_{n=0}^{\infty}n p (1-p)^{n} + \sum_{n=1}^{\infty} p (1-p)^{n-1} = [/math]

[math]= (1-p) \operatorname{E}(\xi) +1 \Rightarrow \operatorname{E}(\xi) = \frac{1}{p}[/math]

• [math] \operatorname{E}(\xi^2) = p\sum_{n=1}^{\infty}n^{2}(1-p)^{n-1} =[/math]

[math] =p\sum_{n=1}^{\infty}n(n+1)(1-p)^{n-1} - p\sum_{n=1}^{\infty}n(1-p)^{n-1} =[/math]

[math] = p\frac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\sum_{n=1}^{\infty}(1-p)^{n+1} + p\frac{\operatorname{d}}{\operatorname{d}p}\sum_{n=1}^{\infty}(1-p)^{n} =[/math]

[math] = p\frac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\sum_{n=0}^{\infty}(1-p)^{n} \cdot (1-p)^2\right) +p\frac{\operatorname{d}}{\operatorname{d}p}\left(\sum_{n=0}^{\infty}(1-p)^{n}\cdot(1-p)\right) =[/math]

[math] = p\frac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\frac{1}{1-(1-p)} \cdot (1-p)^2\right) +p\frac{\operatorname{d}}{\operatorname{d}p}\left(\frac{1}{1-(1-p)}\cdot(1-p)\right) =[/math]

[math] = p\frac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\frac{(1-p)^2}{p}\right) +p\frac{\operatorname{d}}{\operatorname{d}p}\left(\frac{1-p}{p}\right) =[/math]

[math] = p\cdot\frac{2}{p^3} - p\cdot\frac{1}{p^2} = \frac{2}{p^{2}} - \frac{1}{p} = \frac{2-p}{p^{2}}[/math].

Тогда:

[math]\operatorname{D}(\xi)=\operatorname{E}(\xi^2)-(\operatorname{E}(\xi))^2= \frac{2-p}{p^{2}}-\frac{1}{p^2}=\frac{1-p}{p^2}[/math]

Ссылки

• Вайнштейн Ф., Разбиение чисел. Журнал "Квант" № 11, 1988 год
• genfunc.ru
• Wikipedia - Generating function
• Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера

Литература

• Graham, Knuth, and Patashnik: Concrete Mathematics