30
правок
Изменения
Нет описания правки
'''Производящая функция''' (англ. ''generating function'') — это формальный степенной ряд:
<tex>G(z)=\sum_{n=0}^\infty a_n z^n</tex>,
порождающий (производящий) последовательность <tex>(a_0, a_1, a_2, ...\ldots)</tex>.
}}
Метод производящих функций был разработан Эйлером в 1750-х годах.
* Исследования асимптотического поведения последовательности;
* Доказательства тождеств с последовательностями;
* Решения задачи подсчета объектов в комбинаторике. Например, в доказательстве [[Нахождение количества разбиений числа на слагаемые|пентагональной теоремы]] или в задаче нахождения количества расстановок <tex>m</tex> ладей на доске <tex>n</tex> × <tex>n</tex>;* Вычисления бесконечных сумм.
== Примеры производящих функций ==
Рассмотрим производящие функции для различных комбинаторных последовательностей:
* <tex dpi = "180">\prod_{n=1}^\infty (1-x^n)</tex> {{---}} производящая функция для разности количества разбиений числа <tex>n</tex> в четное и нечетное число различных слагаемых. Например коэффициент при <tex>x^5</tex> {{---}} <tex>+1</tex>, потому-что существует два разбиение на четное число различных слагаемых (<tex>4+1</tex>; <tex>3+2</tex>) и одно на нечетное (<tex>5</tex>). Правильность этого легко осознать, если понять, что каждая скобка представляет какое-то слагаемое и мы можем его взять (второе слагаемое {{---}} <tex>-x^k</tex>) или не взять (первое {{---}} <tex>1</tex>). Эта производящая функция используется в комбинаторном доказательстве пентагональной теоремы.
* <tex dpi = "180">\prod_{n=1}^\infty (\dfrac{1}{1+-x^n)}</tex> {{---}} производящая функция для последовательности <tex>d_np_n</tex>, где <tex>d_ip_i</tex> {{---}} количество разбиений числа <tex>i</tex> на различные слагаемые.
* <tex dpi = "180">\prod_{n=1}^\infty (1+x^{2n-1}n)</tex> {{---}} производящая функция для последовательности <tex>l_nd_n</tex>, где <tex>l_id_i</tex> {{---}} количество разбиений на нечётные различные слагаемые. С помощью метода производящих функций можно доказать, что производящие функции последовательностей равны, соответственно <tex>d_n=l_n</tex>:<tex dpi = "180"> \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}...=</tex>
* <tex>\prod_{n=1}^\infty(1+x^{ 2n - 1})</tex> {{---}} производящая функция для последовательности <tex>l_n</tex>, где <tex>l_i</tex>{{---}}
количество разбиений на нечётные слагаемые.С помощью метода производящих функций можно доказать, что производящие функции последовательностей равны, соответственно <tex>d_n = l_n </tex>: <tex>\prod_{n=1}^\infty(1+x^{ n})=\prod_{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=</tex>
<tex dpi = "180">=\fracdfrac{1}{1-x}\fracdfrac{1}{1-x^3}\fracdfrac{1}{1-x^5}...\ldots=\prod_{n=1}^\infty (1+x^{2n-1})</tex>
== Примеры решений задач методом производящих функций ==
=== Решение рекуррентных соотношений ===
Существует целый класс последовательностей, задаваемых рекуррентным соотношением, например, <tex>f_n</tex> {{---}} числа Фибоначчи или <tex>C_n</tex> {{---}} [[Числа Каталана | числа Каталана]]. Метод производящих функций позволяет получить выражение для <tex>a_n</tex> через номер элемента в последовательности в замкнутом виде, то есть в таком виде, что выражение можно вычислить, предполагая, что <tex>z</tex> достаточно мало.
Пусть последовательность <tex>(a_0, a_1, a_2, \ldots)</tex> удовлетворяет некоторому рекуррентному соотношению.Мы хотим получить выражение для <tex>a_n</tex> (при <tex>n \geqslant 0</tex>) в замкнутом виде.Алгоритм получения замкнутого выражения для чисел <tex>a_n</tex>, удовлетворяющих рекуррентному соотношению, с помощью производящих функций состоит из 4 шагов: # Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен <tex>k</tex>, то есть количество предшествующих элементов, требуемых для вычисления элемента с номером <tex>n</tex>, равно <tex>k</tex>):#: <tex>a_0=...\ldots,</tex>#: <tex>a_1=...\ldots,</tex>#: <tex>...\ldots</tex>#: <tex>a_{k-1}=...\ldots,</tex>#: <tex>a_{n}=...\ldots, n \geqslant k.</tex>
# Домножить каждую строчку на <tex>z</tex> в соответствующей степени и просуммировать строчки для всех <tex>n \geqslant 0 </tex>.
# В полученном уравнении привести все суммы <tex>\sum</tex> к замкнутому виду. Получить уравнение для производящей функции.
# Выразить <tex>G(z)</tex> в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням <tex>z</tex>.
Для демонстрации универсальности метода рассмотрим довольно произвольное рекуррентное соотношение:
<tex>a_0=1,</tex>
<tex>a_1=2,</tex>
<tex>a_n=6a_{n-1}-8a_{n-2}+n, n \geqslant 2</tex>
Запишем производящую функцию для этой последовательности и преобразуем правую часть:
<tex>G(z)=a_0+a_1z+\sum_{n=2}^\infty (6a_{n-1}-8a_{n-2}+n) z^n</tex>
<tex>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</tex>
<tex>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</tex>
Для того, чтобы замкнуть последнюю сумму воспользуемся очень важным приемом, который используется при преобразовании производящих функций. Фактически мы имеем дело с последовательностью <tex>nb_n</tex> (в нашем случае последовательность <tex>b_n=(1, 1, 1, ...\ldots)</tex>). Такая последовательность получается путём дифференцирования функции <tex>B(z)</tex>, производящей для <tex>b_n</tex>, с последующим умножением результата на <tex>z</tex>:
<tex dpi = "150">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</tex>
<tex dpi = "150">\sum_{n=2}^\infty n z^n=z \sum_{n=2}^\infty n z^{n-1}= z (\sum_{n=2}^\infty z^n)'</tex>
<tex dpi = "150">\sum_{n=2}^\infty z^n=\sum_{n=0}^\infty z^n-1-z=\fracdfrac{1}{1-z}-1-z=\fracdfrac{z^2}{1-z}</tex>
<tex dpi = "150">z (\fracdfrac{z^2}{1-z})'=\fracdfrac{z^2(2-z)}{(1-z)^2}</tex>
<tex dpi = "150">G(z)=1-4z+6zG(z) - 8z^2G(z)+\fracdfrac{z^2(2-z)}{(1-z)^2}</tex>
<tex dpi = "180">G(z)=\fracdfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}</tex>
Разложим знаменатель на множители и разобьём дробь на сумму простых дробей<ref>[http://www.genfunc.ru/theory/pril04/ О разложении рациональной функции в ряд]</ref>:
<tex> 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}</tex>
Разложим первое слагаемое в ряд, используя расширенные биномиальные коэффициенты <tex dpi = "180"ref>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[http:/3}{(1-z)^2}+\frac{7/9}{1-z}-\frac{1www.genfunc.ru/2}{1-2z}+\frac{7theory/18}{1-4z}pril02/ Расширенные биномиальные коэффициенты]</texref>:
<tex>\dfrac{ 1}{(1-z)^2}=(1-z)^{-2}=\sum_{n=0}^{\infty} {-2\choose n}(-z)^n=</tex>
<tex>=\sum_{n=0}^{\infty} (-1)^n{n+1\choose 1}(-z)^n=\sum_{n=0}^{\infty}(n+1)z^n</tex>
<tex>G(z)=\dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}=</tex>
<tex>=\dfrac{1}{3}\sum_{n=0}^{\infty} (n+1)z^n +\dfrac{7}{9}\sum_{n=0}^{\infty} z^n - \dfrac{1}{2}\sum_{n=0}^{\infty} 2^n z^n + \dfrac{7}{18}\sum_{n=0}^{\infty} 4^n z^n</tex>
<tex>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}</tex>
=== Расчет дисперсии геометрического распределения ===Метод производящих функций также используется для нахождения [[Дисперсия случайной величины | математического ожидания и дисперсии]] различных распределений в теории вероятностей. Например, в геометрическом распределении <ref>[http://ru.wikipedia.org/wiki/%D0%93%D0%B5%D0%BE%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5 Геометрическое распределение]</ref> для нахождения дисперсии <tex dpi = "160">a_n=\fracoperatorname{n+1D}{3}+(\xi)=\fracoperatorname{7E}{9}-(\frac{2xi^n}{2}+)-(\frac{7 \cdot 4^n}operatorname{18E}=\frac{7 (\cdot 4xi))^n+6n+20}{18}-2^{n-1}</tex>нужно найти два мат. ожидания:
* <tex>\operatorname{E}(\xi)=\sum_{n=1}^{\infty}n p(1-p)^{n-1} </tex>
* <tex>\operatorname{E}(\xi^2) = \sum_{n=1}^{\infty}n^{2}p(1-p)^{n-1}</tex>
которые фактически являются производящими функциями последовательностей <tex>1, 2, 3\ldots</tex> и <tex>1, 4, 9\ldots</tex>:
* <tex>\operatorname{ E}(\xi)=\sum_{n=1}^{\infty}n p(1-p)^{n-1} = </tex>
<tex dpi = "160">= \sum_{n=0}^{\infty}n p(1-p)^{n} +\sum_{n=1) }^{\infty} p (1-p)^{n-1} = </tex>
<tex dpi = "160">= \sum_{n=0}^{\infty}n p (1-p)^\operatorname{nE} (\xi) + 1 \Rightarrow \sum_operatorname{nE}(\xi) =\dfrac{1}^{\infty} p (1-p)^{n-1} = </tex>
* <tex>\operatorname{E}(\xi^2) = p\sum_{n=1}^{\infty}n^{2}(1-p)^{n-1} =</tex>
<tex dpi = "160"> = p\fracdfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\sum_{n=01}^{\infty}(1-p)^{n+1} \cdot (1-p)^2\right) +p\fracdfrac{\operatorname{d}}{\operatorname{d}p}\left(\sum_{n=01}^{\infty}(1-p)^{n}\cdot(1-p)\right) =</tex>
<tex dpi = "160"> = p\fracdfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\fracsum_{1n = 0}^{1-\infty}(1-p)^{n} \cdot (1-p)^2\right) +p\fracdfrac{\operatorname{d}}{\operatorname{d}p}\left(\fracsum_{1n = 0}^{1-\infty}(1-p)^{n}\cdot(1-p)\right) =</tex>
<tex dpi = "160"> = p\fracdfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\fracdfrac{ 1}{1-(1-p)} \cdot(1-p)^2}{p}\right) +p\fracdfrac{\operatorname{d}}{\operatorname{d}p}\left(\fracdfrac{ 1}{1-(1-p)}{\cdot(1-p})\right) =</tex>
<tex dpi = "160"> = p\cdotdfrac{\fracoperatorname{d}^{2}}{\operatorname{d}p^3{2}} - p\cdotleft(\fracdfrac{(1}{- p) ^2} = \frac{2p}\right) +p\dfrac{p^\operatorname{2d}} - {\fracoperatorname{1d}{p} = \fracleft(\dfrac{21 -p}{p^{2}}\right) =</tex>.
<tex>= p\cdot\dfrac{2}{p^3} - p\cdot\dfrac{1}{p^2} = \dfrac{2}{p^{2}} - \dfrac{1}{p} = \dfrac{2-p}{p^{2}}</tex>.
Тогда:
<tex dpi = "160">\operatorname{D}(\xi)=\operatorname{E}(\xi^2)-(\operatorname{E}(\xi))^2= \fracdfrac{2-p}{p^{2}}-\fracdfrac{1}{p^2}=\fracdfrac{1-p}{p^2}</tex>
== Приложения ==
=== Примеры простых производящих функций ===
На последнем шаге приведения производящей функции к замкнутому виду требуется разложить полученные слагаемые в ряд. Для этого можно воспользоваться таблицей основных производящих функций<ref>[http://www.genfunc.ru/theory/pril03/ Таблица производящих функций]</ref>.
Все суммы <tex dpi="110">\sum</tex> выполняются по переменной <tex>n</tex> от <tex>0</tex> до <tex>\infty</tex>. Элементы последовательности нумеруются от <tex>0</tex>.
{| class="wikitable" style="width:30cm" border=1
|+
| Последовательность || Производящая функция в виде ряда || Производящая функция в замкнутом виде
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 0, 0,...\ldots)</tex> || <tex>1</tex> || <tex>1</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(0, 0, ...\ldots, 0, 1, 0, 0...\ldots)</tex> (<tex>m</tex> нулей в начале) || <tex>z^m</tex> || <tex>z^m</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 1, 1,...\ldots)</tex> || <tex>\sum z^n</tex> || <tex dpi="160">\fracdfrac{1}{1-z}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 0, 0, ...\ldots, 0, 1, 0, 0, ... \ldots 0, 1, 0, 0...\ldots)</tex> (повторяется через <tex>m</tex>) || <tex>\sum z^{nm}</tex> || <tex dpi="160">\fracdfrac{1}{1-z^m}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, -1, 1, -1,...\ldots)</tex> || <tex>\sum (-1)^nz^n</tex> || <tex dpi="160">\fracdfrac{1}{1+z}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 2, 3, 4,...\ldots)</tex> || <tex>\sum (n+1)z^n</tex> || <tex dpi="160">\fracdfrac{1}{(1-z)^2}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 2, 4, 8, 16,...\ldots)</tex> || <tex>\sum 2^nz^n</tex> || <tex dpi="160">\fracdfrac{1}{(1-2z)^2}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, r, r^2, r^3,...\ldots)</tex> || <tex>\sum r^nz^n</tex> || <tex dpi="160">\fracdfrac{1}{(1-rz)^2}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex dpi="160">(</tex><tex dpi="130">{m\choose 0}, {m\choose 1}, {m\choose 2}, {m\choose 3},...\ldots</tex><tex dpi="160">)</tex> || <tex dpi="140">\sum {m\choose n}</tex> <tex>z^n</tex> || <tex>(1+z)^m</tex>
|-align="left" bgcolor=#FFFFFF
| <tex dpi="160">(</tex><tex dpi="130">1, {{m}\choose m}, {{m+1}\choose m}, {{m+2}\choose m},...\ldots</tex><tex dpi="160">)</tex> || <tex dpi="140">\sum {{m+n-1}\choose n}</tex> <tex>z^n</tex> || <tex dpi="160">\fracdfrac{1}{(1-z)^m}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex dpi="160">(</tex><tex dpi="130">1, {{m+1}\choose m}, {{m+2}\choose m}, {{m+3}\choose m},...\ldots</tex><tex dpi="160">)</tex> || <tex dpi="140">\sum {{m+n}\choose n}</tex> <tex>z^n</tex> || <tex dpi="160">\fracdfrac{1}{(1-z)^{m+1}}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex dpi="140">(0, 1, -\fracdfrac{1}{2}, \fracdfrac{1}{3}, -\fracdfrac{1}{4},...\ldots)</tex> || <tex dpi="160">\sum \fracdfrac{(-1)^{n+1}}{n}</tex> <tex>z^n</tex> || <tex>\ln(1+z)</tex>
|-align="left" bgcolor=#FFFFFF
| <tex dpi="140">(1, 1, \fracdfrac{1}{2}, \fracdfrac{1}{6}, \fracdfrac{1}{24},...\ldots)</tex> || <tex dpi="160">\sum \fracdfrac{1}{n!}</tex> <tex>z^n</tex> || <tex dpi="140">e^z</tex>
|}
* [http://kvant.mirror1.mccme.ru/1988/11/razbienie_chisel.htm Вайнштейн Ф., Разбиение чисел. Журнал "Квант" № 11, 1988 год]
* [http://www.genfunc.ru/ Производящие функции]
* [http://en.wikipedia.org/wiki/Generating_function Wikipedia {{- --}} Generating function]
* [[Нахождение количества разбиений числа на слагаемые|Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
* Graham, Knuth, and Patashnik: Concrete Mathematics
