Изменения

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

* Компактной записи информации о последовательности;.* Нахождения зависимости <tex>a_n(n)</tex> для последовательности <tex>a_n</tex>, заданной рекуррентным соотношением. Например, для чисел Фибоначчи;.* Нахождения рекуррентного соотношения для последовательности {{---}} вид производящей функции может помочь найти формулу;.* Исследования асимптотического поведения последовательности;.* Доказательства тождеств с последовательностями;.* Решения задачи подсчета объектов в комбинаторике. Например, в доказательстве [[Нахождение количества разбиений числа на слагаемые|пентагональной теоремы]] или в задаче нахождения количества расстановок <tex>m</tex> ладей на доске <tex>n</tex>&nbsp;×&nbsp;<tex>\times n</tex>;.* Вычисления бесконечных сумм.  

* <tex dpi = "180">\prod_prod\limits_{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 \frac{1}{1-x^n}</tex> {{---}} производящая функция для последовательности <tex>p_n</tex>, где <tex>p_i</tex> {{---}} количество разбиений числа <tex>i</tex> на слагаемые.

* <tex dpi = "180">\prod_prod\limits_{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_prod\limits_{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>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>\sum</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_sum\limits_{n=2}^\infty (6a_{n-1}-8a_{n-2}+n) z^n</tex>

<tex>G(z)=a_0+a_1z+6\sum_sum\limits_{n=2}^\infty a_{n-1}z^n - 8\sum_sum\limits_{n=2}^\infty a_{n-2}z^n+\sum_sum\limits_{n=2}^\infty n z^n</tex>

<tex>G(z)=a_0+a_1z+6z\sum_sum\limits_{n=1}^\infty a_{n}z^n - 8z^2\sum_sum\limits_{n=0}^\infty a_{n}z^n+\sum_sum\limits_{n=2}^\infty n z^n</tex>

<tex>G(z)=a_0+a_1z+6z(G(z)-a_0) - 8z^2G(z)+\sum_sum\limits_{n=2}^\infty n z^n</tex>

<tex>G(z)=1-4z+6zG(z) - 8z^2G(z)+\sum_sum\limits_{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_sum\limits_{n=0}^\infty b_n z^n)'=z\sum_sum\limits_{n=1}^\infty nb_n z^{n-1}=\sum_sum\limits_{n=0}^\infty nb_n z^n</tex>

<tex dpi = "150">\sum_sum\limits_{n=2}^\infty n z^n=z \sum_sum\limits_{n=2}^\infty n z^{n-1}= z (\sum_sum\limits_{n=2}^\infty z^n)'</tex>

<tex dpi = "150">\sum_sum\limits_{n=2}^\infty z^n=\sum_sum\limits_{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 >G(z)= "180"\dfrac{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)=\fracdfrac{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> Разложим первое слагаемое в ряд, используя расширенные биномиальные коэффициенты <ref>[http://www.genfunc.ru/theory/pril02/ Расширенные биномиальные коэффициенты]</ref>:

Разложим знаменатель на множители и разобьём дробь на сумму простых дробей<reftex>[http://www.genfunc.ru/theory/pril04/ О разложении рациональной функции в ряд]\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</reftex>:

<tex dpi = "180">G(z)=\fracdfrac{1-6z+11z^2-5z^/3}{(1-6z+8zz)^2)(}+\dfrac{7/9}{1-z)^2}=-\fracdfrac{1-6z+11z^/2-5z^3}{(1-2z)(}+\dfrac{7/18}{1-4z)(1-z)^2}=\fracdfrac{1/}{3}\sum\limits_{n=0}^{\infty} (n+1-)z)^2}n +\fracdfrac{7/}{9}\sum\limits_{n=0}^{1-\infty} z}^n -\fracdfrac{1/}{2}\sum\limits_{n=0}^{1-2z\infty}2^n z^n +\fracdfrac{7/}{18}\sum\limits_{n=0}^{1-4z\infty}4^n z^n</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">\fracoperatorname{1D}{(1-z\xi)^2}=(1-z)^\operatorname{-2E}=(\sum_{n=0}xi^{2)-(\infty} operatorname{-2\choose nE}(-z\xi))^n=2</tex>нужно найти два мат. ожидания:

* <tex dpi = "160">=\sum_{n=0}^operatorname{\inftyE} (-1)^n{n+1\choose 1}(-zxi)^n=\sum_sum\limits_{n=01}^{\infty}n p(n+1-p)z^{n-1} </tex>

* <tex dpi = "160">G(z)=\fracoperatorname{1/3E}{(1-z)\xi^2}+) = \sum\fraclimits_{7/9n=1}^{1-z\infty}-\fracn^{1/2}{p(1-2z}+\frac{7/18}p)^{n-1-4z}=</tex>

которые фактически являются производящими функциями последовательностей <tex dpi = "160">=\frac{1}{, 2, 3}\sum_{n=0}^{\infty} (n+ldots</tex> и <tex>1)z^n +\frac{7}{, 4, 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^nldots</tex>:

* <tex dpi = "160">a_n=\fracoperatorname{n+1E}{3}+(\xi)=\frac{7}{9}-sum\fraclimits_{2^n=1}^{2}+\frac{7 \cdot 4^ninfty}{18}=\frac{7 \cdot 4^n+6n+20}{18}p(1-2p)^{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>= \sum\operatornamelimits_{D}(\xi)n=\operatorname{E0}(\xi^2)-({\operatorname{Einfty}(\xin+1)p(1-p)^2{n} = </tex> нужно найти два мат. ожидания:

* <tex dpi >= "160">(1-p) \operatorname{E}(\xi) +1 \Rightarrow \operatorname{E}(\xi)=\sum_dfrac{n=1}^{\infty}n p (1-p)^{n-1} </tex>

*<tex dpi = "160"> \operatorname{E}(\xi^2) = p\sum_sum\limits_{n=1}^{\infty}n^{2}p(1-p)^{n-1}=</tex>

которые фактически являются производящими функциями последовательностей <tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\sum\limits_{n=1}^{\infty}(1, 2, 3...</tex> и <tex>-p)^{n+1} + p\dfrac{\operatorname{d}}{\operatorname{d}p}\sum\limits_{n=1}^{\infty}(1, 4, 9...-p)^{n} =</tex>:

* <tex dpi >= "160">p\dfrac{\operatorname{Ed}^{2}}({\xi)=\sum_operatorname{n=1d}p^{2}}\inftyleft(\dfrac{ 1}n {1-(1-p )} \cdot(1-p)^2\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\dfrac{n1}{1-(1-p)} \cdot(1-p)\right) = </tex>

<tex dpi = "160">= p\dfrac{\sum_operatorname{n=0d}^{2}}{\inftyoperatorname{d}p^{2}}\left(\dfrac{ (n+1- p) ^ 2}{p}\right) +p \dfrac{\operatorname{d}}{\operatorname{d}p}\left(\dfrac{ 1-p)^}{np} \right) = </tex>

<tex dpi = "160">= p\sum_cdot\dfrac{n=02}{p^{\infty3}n - p (\cdot\dfrac{1-}{p)^{n2} + = \sum_dfrac{n=12}{p^{2}} - \inftydfrac{1} {p (1} = \dfrac{2-p)}{p^{n-12}} = </tex>.

* === Пример задачи на нахождение производящей функции ==={{Задача| about = | definition = Рассмотрим множество путей на прямой, состоящих из шагов длины <tex dpi = "160"> \operatorname{E1</tex> вправо и влево. Найдите производящую функцию для числа таких путей из <tex>n</tex> шагов, начинающихся в <tex>0</tex> и оканчивающихся в <tex>0</tex>.}}(Заметим, что для того, чтобы закончить путь в <tex>0</tex>, необходимо совершить равное число шагов вправо и влево. Тогда задача сводится к тому, чтобы выбрать <tex>\xi^2) = p\sum_dfrac{n=1}^{\infty2}</tex> позиций для, например, шагов вправо из всего <tex>n</tex> шагов. Тогда ответом будет сумма от нуля до бесконечности по <tex>n</tex> всех <tex>C^{2n}(1-p)^_{n-12n} =</tex> . То есть:<tex dpi = "160"> g(x) =p\sum_sum\limits_{n=10}^{\infty}n(n+1)(1-p)C^{n-1} - p\sum__{n=12n}x^{\infty}n(1-p)^{n-1} =</tex> Рассмотрим <tex dpi = "160"> f(x) = p\frac{sum\operatornamelimits_{d0}^{2}}{\operatorname{dinfty}pC_n x^n </tex>, где <tex>C_n</tex> {{2---}}[[Числа Каталана | число Каталана]]. Тогда, заметим что <tex>f'(x) = \sum_sum\limits_{n=10}^{\infty}(1-p)n C_n x^{n+-1} + p</tex>. Так как <tex>C_n = \fracdfrac{\operatorname{d}1}{\operatorname{d}p}\sum_{n=+1}^C_{\infty2n}^n </tex>, то справедливо равенство:<tex>g(x) = (n+1-p)^{n} f(x) =xf'(x) + f(x)</tex>

Мы знаем, что производящая функция для чисел Каталана равна <tex dpi = "160"> f(x) = p\frac{\operatorname{d}^{2}}{\operatornamedfrac{d}p^{2}}\left(\sum_{n=0}^{\infty}(1-p)^\sqrt{n} \cdot (1-p)^2\right) +p\frac{\operatorname{d4x}}{\operatorname{d}p}\left(\sum_{n=0}^{\infty2x}</tex>. Найдем <tex>f'(1-px)^{n}\cdot(1-p)\right) =</tex>.

<tex dpi = "160"> f'(x) = p\fracdfrac{\operatornamedfrac{d4x}^{2\sqrt{1-4x}}{- 2 + 2\operatornamesqrt{d1-4x}p}{4x^{2}}\left(= \frac{1}dfrac{1-(12x -p)} \cdot (sqrt{1-p)^2\right) +p\frac{\operatorname{d4x}}{2x^2 \operatorname{d}p}\left(\fracsqrt{1-4x}{1-(1-p)}\cdot(1-p)\right) =</tex>

<tex dpi = "160"> g(x) = p\cdotdfrac{1 - 2x - \fracsqrt{21-4x}}{p^3} - p2x \cdot\fracsqrt{1-4x}{p^2} = + \fracdfrac{2}{p^{2}} 1- \fracsqrt{1-4x}}{p2x} = \fracdfrac{2-p1}{p^\sqrt{21 - 4x}}</tex>.

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

<!--easy биномы увеличить, но так имхо лучше--->На последнем шаге приведения производящей функции к замкнутому виду требуется разложить полученные слагаемые в ряд. Для этого можно воспользоваться таблицей основных производящих функций<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>.

| '''Последовательность ''' || '''Производящая функция в виде ряда ''' || '''Производящая функция в замкнутом виде'''|-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>

| <tex>(1, 01, 01,...\ldots)</tex> || <tex>1\sum\limits z^n</tex> || <tex>\dfrac{1}{1-z}</tex>

| <tex>(1, 0, 0, ...\ldots, 0, 1, 0, 0..., \ldots 0, 1, 0, 0\ldots)</tex> (повторяется через <tex>m</tex> нулей в начале) || <tex>\sum\limits z^m{nm}</tex> || <tex>\dfrac{1}{1-z^m}</tex>

| <tex>(1, -1, 1, -1,...\ldots)</tex> || <tex>\sum z\limits (-1)^nz^n</tex> || <tex dpi="160">\fracdfrac{1}{1-+z}</tex>

| <tex>(1, 02, 03, ...4, 0, 1, 0, 0, ... 0, 1, 0, 0...\ldots)</tex> (повторяется через <tex>m</tex>) || <tex>\sum \limits (n+1)z^{nm}n</tex> || <tex dpi="160">\fracdfrac{1}{(1-z)^m2}</tex>

| <tex>(1, -12, 4, 18, -116,...\ldots)</tex> || <tex>\sum (-1)\limits 2^nz^n</tex> || <tex dpi="160">\fracdfrac{1}{(1+z-2z)}</tex>

| <tex>(1, r, r^2, r^3, 4,...\ldots)</tex> || <tex>\sum (n+1)z\limits r^nz^n</tex> || <tex dpi="160">\fracdfrac{1}{(1-zrz)^2}</tex>

| <tex>(</tex><tex>{m\choose 0}, {m\choose 1}, {m\choose 2}, 4{m\choose 3}, 8, 16,...\ldots</tex><tex>)</tex> || <tex>\sum 2^nz\limits {m\choose n}</tex> <tex>z^n</tex> || <tex dpi="160">\frac{1}{(1-2z+z)^2}m</tex>

| <tex>(</tex><tex>1, r{{m}\choose m}, r^{{m+1}\choose m}, {{m+2}\choose m}, r^3,...\ldots</tex><tex>)</tex> || <tex>\sum r^nz\limits {{m+n-1}\choose n}</tex> <tex>z^n</tex> || <tex dpi="160">\fracdfrac{1}{(1-rzz)^2m}</tex>

| <tex dpi="160">(</tex><tex dpi="130">1, {{m+1}\choose 0m}, {{m+2}\choose 1m}, {{m+3}\choose 2m}, {m\choose 3},...ldots</tex><tex dpi="160">)</tex> || <tex dpi="140">\sum \limits {{m+n}\choose n}</tex> <tex>z^n</tex> || <tex>\dfrac{1}{(1+-z)^{m+1}}</tex>

| <tex dpi="160">(</tex><tex dpi="130">0, 1, -\dfrac{1}{m2}, \choose m}, {dfrac{m+1}\choose m{3}, -\dfrac{1}{m+24},\choose m},...</tex><tex dpi="160">ldots)</tex> || <tex dpi="140">\sum \limits \dfrac{(-1)^{mn+n-1}\choose }{n}</tex> <tex>z^n</tex> || <tex dpi="160">\frac{1}{ln(1-+z)^m}</tex>

| <tex dpi="160">(</tex><tex dpi="130">1, 1, \dfrac{{m+1}\choose m{2}, \dfrac{1}{m+26}, \choose mdfrac{1}, {{m+324},\choose m},...</tex><tex dpi="160">ldots)</tex> || <tex dpi="140">\sum \limits \dfrac{1}{m+n}\choose n!}</tex> <tex>z^n</tex> || <tex dpi="160">\frac{1}{(1-e^z)^{m+1}}</tex>

| <tex dpi="140">(0, 1, -\fracdfrac{1}{2!}m^2, \fracdfrac{1}{34!}m^4, -\fracdfrac{1}{46!}m^6, \dfrac{1}{8!}m^8,...\ldots)</tex> || <tex dpi="160">\sum \fraclimits \dfrac{(-1)^{n+1}}{n(2n)!}</tex> <tex>zm^n{(2n)}</tex> || <tex>\ln(1+z)cos m</tex>

| <tex dpi="140">(1m, -\dfrac{1}{3!}m^3, \fracdfrac{1}{25!}m^5, -\fracdfrac{1}{67!}m^7, \fracdfrac{1}{249!}m^9,...\ldots)</tex> || <tex dpi="160">\sum \fraclimits \dfrac{1}{n(2n-1)!}</tex> <tex>zm^n{(2n-1)}</tex> || <tex dpi="140">e^z\sin m</tex>

* [http://www.genfunc.ru/ genfunc.ruПроизводящие функции]* [http://en.wikipedia.org/wiki/Generating_function Wikipedia {{--- }} Generating function]