Изменения

'''Производя́щая фу́нкция Производящая функция''' (англ. ''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&nbsp;×&nbsp;\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; 3+2) </tex> и одно на нечетное (<tex>5</tex>). Правильность этого легко осознать, если понять, что каждая скобка представляет какое-то слагаемое и мы можем его взять (второе слагаемое {{---}} <tex>-x^k</tex>) или не взять (первое {{---}} <tex>1</tex>). Эта производящая функция используется в комбинаторном доказательстве пентагональной теоремы.

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

* <tex dpi = "180">\prod_prod\limits_{n=1}^\infty (1+x^{2n-1})^{-1}</tex> {{---}} производящая функция для последовательности <tex>l_n</tex>, где <tex>l_i</tex> {{---}} количество число разбиений на нечётные слагаемые. С помощью метода производящих функций можно доказать, что производящие функции последовательностей равны, соответственно <tex>d_n=l_n</tex>:<tex dpi = "180"> \prod_prod\limits_{n=1}^\infty (1+x^{n})=\prod_prod\limits_{n=1}^\infty \fracdfrac{1-x^{2n}}{1-x^n}=\fracdfrac{1-x^2}{1-x}\fracdfrac{1-x^4}{1-x^2}\fracdfrac{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_prod\limits_{n=1}^\infty (1+x^{2n-1})^{-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>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> Запишем производящую функцию для этой последовательности и преобразуем правую часть:

1<tex>G(z)Записать рекуррентное соотношение и начальные данные для него в следующем виде =a_0+a_1z+\sum\limits_{n=2}^\infty(если порядок соотношения равен k, то есть количество предшествующих элементов, требуемых для вычисления элемента с номером 6a_{ n - 1}-8a_{n-2}+n, равно k):z^n</tex>

<tex>a_1G(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</tex>

<tex>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+\ge k.sum\limits_{n=2}^\infty n z^n</tex>

3)В полученном уравнении привести все суммы <tex>G(z)=a_0+a_1z+6z(G(z)-a_0) - 8z^2G(z)+\sum\limits_{n=2}^\infty n z^n</tex> к замкнутому виду. Получить уравнение для производящей функции.

Для демонстрации универсальности метода рассмотрим довольно произвольное рекуррентное соотношение:<tex>G(z)=1-4z+6zG(z) - 8z^2G(z)+\sum\limits_{n=2}^\infty n z^n</tex> 

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

<tex>a_nzB'(z)=6a_z(\sum\limits_{n=0}^\infty b_n z^n)'=z\sum\limits_{n-= 1}-8a_^\infty nb_n z^{n-21}+=\sum\limits_{n, =0}^\infty nb_n z^n \ge 2</tex>

<tex dpi > G(z) = "150">\sum_dfrac{n=1-6z+11z^2-5z^3}{(1-6z+8z^\infty n 2)(1-z)^n2}=z \sum_dfrac{n=1-6z+11z^2-5z^3}{(1-2z)(1-4z)(1-z)^2}=\infty n dfrac{1/3}{(1-z)^2}+\dfrac{n7/9}{1-1z}= z (-\sum_dfrac{n=1/2}^{1-2z}+\infty z^n)'dfrac{7/18}{1-4z}</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 = "150">G\operatorname{D}(z\xi)=1-4z+6zG\operatorname{E}(z\xi^2) - 8z^2G(z)+\fracoperatorname{z^2E}(2-z\xi)}{(1-z)^2}</tex>нужно найти два мат. ожидания:

Это уравнение для производящей функции. Из него выражаем * <tex>G\operatorname{E}(z\xi)=\sum\limits_{n=1}^{\infty}n p(1-p)^{n-1} </tex>:

* <tex dpi = "180">G\operatorname{E}(z\xi^2)=\fracsum\limits_{n=1-6z+11z}^2-5z{\infty}n^3}{(1-6z+8z^2)}p(1-zp)^2{n-1}</tex>

Разложим знаменатель на множители которые фактически являются производящими функциями последовательностей <tex>1, 2, 3\ldots</tex> и [http://www.genfunc.ru/theory/pril04<tex>1, 4, 9\ldots</ разобьём дробь на сумму простых дробей]tex>:

* <tex dpi = "180">G(z)=\fracoperatorname{1-6z+11z^2-5z^3E}{(1-6z+8z^2\xi)(1-z)^2}=\fracsum\limits_{n=1-6z+11z^2-5z}^3}{(1-2z)(1-4z)(1-z)^2}=\frac{1/3infty}{n p(1-zp)^2}+\frac{7/9}{1n-z}-\frac{1/2}{1-2z}+\frac{7/18}{1-4z}= </tex>

Разложим первое слагаемое в ряд, используя [http:<tex>= \sum\limits_{n=0}^{\infty}(n+1) p(1-p)^{n} = <//www.genfunc.ru/theory/pril02/ расширенные биномиальные коэффициенты]:tex>

<tex dpi >= "160">\frac{1}{(1-zp)^2\operatorname{E}=(\xi) +1-z)^\Rightarrow \operatorname{-2E}(\xi) =\sum_dfrac{n=01}^{\inftyp} {-2\choose n}(-z)^n=</tex>

* <tex dpi = "160">=\sum_operatorname{n=0E}^{(\infty} (-1)xi^n{n+1\choose 1}(-z2)^n=p\sum_sum\limits_{n=01}^{\infty}n^{2}(n+1-p)z^{n-1} =</tex>

<tex dpi = "160">G(z)=p\dfrac{\operatorname{d}^{2}}{\fracoperatorname{d}p^{2}}\sum\limits_{n=1/3}^{\infty}(1-zp)^2{n+1}+p\fracdfrac{7/9\operatorname{d}}{1-z\operatorname{d}p}-\fracsum\limits_{n=1/2}^{1-2z}+\frac{7/18infty}{(1-4zp)^{n}=</tex>

<tex dpi = "160">=p\fracdfrac{1}{3}\sum_operatorname{n=0d}^{\infty2} (n+1)z^n +\frac{7}{9}\sum_operatorname{n=0d}p^{2}}\infty} z^n - left(\fracdfrac{1}{21-(1-p)}\sum_{n=0}cdot(1-p)^2\right) +p\dfrac{\inftyoperatorname{d} 2^n z^n + }{\fracoperatorname{7d}{18p}\sum_left(\dfrac{n=01}^{1-(1-p)}\cdot(1-p)\infty} 4^n z^nright) =</tex>

<tex dpi = "160">a_n=p\fraccdot\dfrac{n+12}{p^3}+- p\cdot\fracdfrac{71}{9p^2}-= \fracdfrac{2}{p^n}{2}+} - \fracdfrac{7 \cdot 4^n1}{18p}=\fracdfrac{7 \cdot 4^n+6n+202-p}{18}-2p^{n-12}}</tex>.

=== Расчет дисперсии геометрического распределения ===Метод производящих функций также используется для нахождения математического ожидания и дисперсии различных распределений в теории вероятностей. Например, в [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 геометрическом распределении] для нахождения дисперсии <tex>D(\xi)=E(\xi^2)-(E(\xi))^2</tex> нужно найти два мат. ожиданияТогда:

которые фактически являются производящими функциями последовательностей === Пример задачи на нахождение производящей функции ==={{Задача| about = | definition = Рассмотрим множество путей на прямой, состоящих из шагов длины <tex>1</tex> вправо и влево. Найдите производящую функцию для числа таких путей из <tex>n</tex> шагов, начинающихся в <tex>0</tex> и оканчивающихся в <tex>0</tex>.}}Заметим, что для того, чтобы закончить путь в <tex>0</tex>, необходимо совершить равное число шагов вправо и влево. Тогда задача сводится к тому, чтобы выбрать <tex>\dfrac{n}{2}</tex> позиций для, например, 3.шагов вправо из всего <tex>n</tex> шагов.Тогда ответом будет сумма от нуля до бесконечности по <tex>n</tex> всех <tex>C^{n}_{2n}</tex>.То есть:<tex>g(x) = \sum\limits_{0}^{\infty} C^{n}_{2n} x^n</tex> и Рассмотрим <tex>f(x) = \sum\limits_{0}^{\infty} C_n x^n </tex>1, 4где <tex>C_n</tex> {{---}} [[Числа Каталана | число Каталана]]. Тогда, 9..заметим что <tex>f'(x) = \sum\limits_{0}^{\infty} n C_n x^{n-1} </tex>.Так как <tex>C_n = \dfrac{1}{n+1} C_{2n}^n </tex>, то справедливо равенство:<tex>g(x) = (n+1)f(x) = xf'(x) + f(x)</tex>

* <tex dpi >f'(x) = "160">\operatornamedfrac{\dfrac{E4x}({\xi)=sqrt{1-4x}} - 2 + 2\sum_sqrt{n=1-4x}}{4x^2} = \dfrac{1 - 2x - \infty}n p (sqrt{1-p)4x}}{2x^2 \sqrt{n1-14x}} = </tex>

<tex dpi = "160">g(x) = \sum_dfrac{1 - 2x - \sqrt{n=01-4x}}^{2x \inftysqrt{1-4x}}n p (+ \dfrac{1-\sqrt{1-p)^4x}}{n2x} + = \sum_dfrac{n=1}^{\infty} p (sqrt{1-p)^4x}}</tex> {{Задача| about = | definition = Рассмотрим множество путей на прямой, состоящих из шагов длины <tex>1</tex> вправо и влево. Найдите производящую функцию для числа таких путей из <tex>n-1} = </tex>шагов, начинающихся и оканчивающихся в <tex>0</tex> и не заходящих в отрицательную полупрямую.}}

* <tex dpi = "160"> \operatorname{E}(\xi^2) = p\sum_{nПриложения =1}^{\infty}n^{2}(1-p)^{n-1} =</tex> <tex dpi = "160"> =p\sum_{n=1}^{\infty}n(n+1)(1Примеры простых производящих функций ===<!-p)^{n-1} easy биномы увеличить, но так имхо лучше- p\sum_{n=1}^{\infty}n(1-p)^{n-1} =</tex> На последнем шаге приведения производящей функции к замкнутому виду требуется разложить полученные слагаемые в ряд. Для этого можно воспользоваться таблицей основных производящих функций <tex dpi = "160"ref> = 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} =[http://www.genfunc.ru/theory/pril03/ Таблица производящих функций]</texref>.

Все суммы выполняются по переменной <tex dpi >n</tex> от <tex>0</tex> до <tex>\infty</tex>. Элементы последовательности нумеруются от <tex>0</tex>. {| class="wikitable" style="width:30cm" border=1|+|-align="center" bgcolor=#EEEEFF| '''Последовательность''' || '''Производящая функция в виде ряда''' || '''Производящая функция в замкнутом виде'''|-align= "160left"bgcolor=#FFFFFF| <tex>(1, 0, 0,\ldots)</tex> || <tex>1</tex> || <tex>1</tex> |-align="left" bgcolor= p#FFFFFF| <tex>(0, 0, \frac{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\limits z^n</tex> || <tex>\operatornamedfrac{d1}{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\limits z^{2nm}</tex> || <tex>\dfrac{1}{1-z^m}</tex>|-align="left" bgcolor=#FFFFFF| <tex>(1, -1, 1, -1,\ldots)</tex> || <tex>\sum\operatornamelimits (-1)^nz^n</tex> || <tex>\dfrac{d1}p{1+z}</tex>|-align="left" bgcolor=#FFFFFF| <tex>(1, 2, 3, 4,\ldots)</tex> || <tex>\sum\limits (n+1)z^n</tex> || <tex>\dfrac{1}{(1-z)^2}</tex>|-align="left" bgcolor=#FFFFFF| <tex>(1, 2, 4, 8, 16,\ldots)</tex> || <tex>\sum\limits 2^nz^n</tex> || <tex>\dfrac{1}\{(1-2z)}</tex>|-align="left" bgcolor=#FFFFFF| <tex>(1, r, r^2, r^3,\sum_ldots)</tex> || <tex>\sum\limits r^nz^n</tex> || <tex>\dfrac{1}{n(1-rz)}</tex>|-align="left" bgcolor=#FFFFFF| <tex>(</tex><tex>{m\choose 0}^, {m\choose 1}, {m\choose 2}, {m\choose 3},\ldots</tex><tex>)</tex> || <tex>\sum\limits {m\inftychoose n}</tex> <tex>z^n</tex> || <tex>(1+z)^m</tex>|-palign="left" bgcolor=#FFFFFF| <tex>(</tex><tex>1, {{m}\choose m}, {{m+1}\choose m}, {{m+2}\choose m},\ldots</tex><tex>)^</tex> || <tex>\sum\limits {{m+n-1} \cdot choose n}</tex> <tex>z^n</tex> || <tex>\dfrac{1}{(1-pz)^m}</tex>|-align="left" bgcolor=#FFFFFF| <tex>(</tex><tex>1, {{m+1}\choose m}, {{m+2}\choose m}, {{m+3}\choose m},\rightldots</tex><tex>) </tex> || <tex>\sum\limits {{m+pn}\fracchoose n}</tex> <tex>z^n</tex> || <tex>\dfrac{1}{(1-z)^{m+1}}</tex>|-align="left" bgcolor=#FFFFFF| <tex>(0, 1, -\operatornamedfrac{d1}{2}, \dfrac{1}{3}, -\operatornamedfrac{d1}p{4},\ldots)</tex> || <tex>\sum\limits \dfrac{(-1)^{n+1}}{n}</tex> <tex>z^n</tex> || <tex>\ln(1+z)</tex>|-align="left" bgcolor=#FFFFFF| <tex>(1, 1, \sum_dfrac{1}{2}, \dfrac{1}{6}, \dfrac{1}{24},\ldots)</tex> || <tex>\sum\limits \dfrac{1}{n!}</tex> <tex>z^n</tex> || <tex>e^z</tex>|-align=0"left" bgcolor=#FFFFFF| <tex>(1, -\dfrac{1}{2!}m^2, \dfrac{1}{4!}m^4, -\dfrac{1}{6!}m^6, \dfrac{1}{8!}m^8,\ldots)</tex> || <tex>\sum\limits \inftydfrac{1}{(2n)!}</tex> <tex>m^{(2n)}</tex> || <tex>\cos m</tex>|-align="left" bgcolor=#FFFFFF| <tex>(m, -\dfrac{1}{3!}m^3, \dfrac{1}{5!}m^5, -p)\dfrac{1}{7!}m^7, \dfrac{1}{n9!}m^9,\ldots)</tex> || <tex>\sum\limits \cdotdfrac{1}{(2n-1)!}</tex> <tex>m^{(2n-p1)}</tex> || <tex>\right) =sin m</tex>|}

<tex dpi = "160"> = 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) См. также ==</tex>

<tex dpi = "160"> = p\cdot\frac{2}{p^3} - p\cdot\frac{1}{p^2} Примечания = \frac{2}{p^{2}} - \frac{1}{p} = \frac{1}{p^{2}}<references/tex>.

== Ссылки Источники информации ==

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