Изменения

'''Производя́щая фу́нкция Производящая функция''' (англ. ''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>\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> \prod\limits_{n=1}^\infty \dfrac{1}{1-x^n}</tex> {{---}} производящая функция для последовательности <tex>p_n</tex>, где <tex>p_i</tex> {{---}} число разбиений числа <tex>i</tex> на слагаемые. * <tex>\prod\limits_{ n = 1}^\infty(1+x^n)</tex> {{---}} производящая функция для последовательности <tex>d_n</tex>, где <tex>d_i</tex> {{---}} число разбиений на различные слагаемые. * <tex>\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>\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=</tex>  <tex>=\dfrac{1}{1-x}\dfrac{1}{1-x^3}\dfrac{1}{1-x^5}\ldots=\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>\prod_{na_1=1}^\infty \frac{1}{1-x^n}</tex> {{---}} производящая функция для последовательности <tex>p_n</tex>2, где <tex>p_i</tex> {{---}} количество разбиений числа i на слагаемые.

* <tex>\prod_a_n= 6a_{n=- 1}^\infty (1+x^-8a_{n)</tex> {{---2}} производящая функция для последовательности <tex>d_n</tex>+n, где <tex>d_in \geqslant 2</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 \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>G(z)=a_0+a_1z+\frac{1}{1-x}sum\fraclimits_{1n=2}{1-x^3}\fracinfty(6a_{n - 1}{1-x^5}...=\prod_8a_{n=1-2}^\infty (1+xn) z^{2n-1})n</tex>

Метод производящих функций также используется для нахождения математического ожидания и дисперсии различных распределений в теории вероятности. Например в геометрическом распределении c p=1/2 для нахождения дисперсии <tex>DG(z)=a_0+a_1z+6\sum\xi)limits_{n=E(2}^\xiinfty a_ { n-1}z^n - 8\sum\limits_{n=2)}^\infty a_ { n-(E(2}z^n+\sum\limits_{n=2}^\xi))infty n z^2n</tex> нужно найти два мат. ожидания:

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

Существует целый класс последовательностей, задаваемых рекуррентным соотношением, например, <tex>f_n</tex> {{-G(z)=a_0+a_1z+6z(G(z)-a_0) -}} числа Фибоначчи или <tex>C_n</tex> 8z^2G(z)+\sum\limits_{{---}n=2} числа Каталана. Метод производящих функций позволяет получить выражение для <tex>a_n^\infty n z^n</tex> в замкнутом виде.

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

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

<tex>a_zB'(z)=z(\sum\limits_{n=0}^\infty b_n z^n)'=..., z\sum\limits_{ n = 1}^\ge k.infty nb_n z^{n-1}=\sum\limits_{n=0}^\infty nb_n z^n</tex>

Для демонстрации универсальности метода рассмотрим довольно произвольное рекуррентное соотношение<tex>\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)'</tex>  <tex>\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}</tex>  <tex>z(\dfrac{ z ^ 2}{1-z})'=\dfrac{z^2(2-z)}{(1-z)^2}</tex>  Таким образом, наше последнее слагаемое примет вид:  <tex>G(z)=1-4z+6zG(z) - 8z^2G(z)+\dfrac{z^2(2-z)}{(1-z)^2}</tex>

Это уравнение для производящей функции. Из него выражаем <tex>a_1=2,G(z)</tex>:

Разложим знаменатель на множители и разобьём дробь на сумму простых дробей <texref>G(z)=a_0+a_1z+\sum_{n=2}^\infty (6a_{n-1}-8a_{n-2}+n) z^n[http://www.genfunc.ru/theory/pril04/ О разложении рациональной функции в ряд]</texref>:

Разложим первое слагаемое в ряд, используя расширенные биномиальные коэффициенты <texref>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[http://www.genfunc.ru/theory/pril02/ Расширенные биномиальные коэффициенты]</texref>:

<tex>G\dfrac{ 1}{(1-z)^2}=a_0+a_1z+6z(1-z)^{-2}=\sum\sum_limits_{n=10}^{\infty a_} {-2\choose n}(-z)^n - 8z^2=\sum\sum_limits_{n=0}^{\infty a_} (-1)^n{n+1\choose 1}(-z)^n+=\sum\sum_limits_{n=20}^{\infty }(n +1)z^n</tex>

<tex>G(z)=a_0+a_1z+6z(G\dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-a_0) z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1- 8z4z}=\dfrac{1}{3}\sum\limits_{n=0}^2G{\infty} (n+1)z)^n +\sum_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</tex>

<tex>G(z)a_n=\dfrac{n+1-4z}{3}+6zG(z) \dfrac{7}{9}- 8z\dfrac{2^2G(z)n}{2}+\sum_dfrac{7 \cdot 4^n}{18}=2}\dfrac{7 \cdot 4^\infty n z+6n+20}{18}-2^{n-1}</tex>

<tex>\sum_{n=2}^\infty z^n=sum\sum_limits_{n=0}^{\infty z^}(n-1-z=\frac{1}{+1-z}-) p(1-z=\frac{zp)^2}{1-zn}= </tex>

<tex>z = (1-p) \fracoperatorname{z^2E}(\xi) +1 \Rightarrow \operatorname{1-zE}(\xi)'=\fracdfrac{z^2(2-z)1}{(1-z)^2p}</tex>

<tex>G(z)=1-4z+6zG(z) - 8zp\dfrac{\operatorname{d}^2G(z)+{2}}{\fracoperatorname{zd}p^{2}}\sum\limits_{n=1}^{\infty}(21-zp)^{n+1} + p\dfrac{\operatorname{d}}{\operatorname{d}p}\sum\limits_{n=1}^{\infty}(1-zp)^2{n}=</tex>

Это уравнение для производящей функции. Из него выражаем <tex>G= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(z\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)=</tex>:

<tex>G(z)=p\fraccdot\dfrac{1-6z+11z^2-5z}{p^3}- p\cdot\dfrac{(1-6z+8z}{p^2} = \dfrac{2}{p^{2)(}} - \dfrac{1}{p} = \dfrac{2-z)p}{p^{2}}</tex>.

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

Мы знаем, что производящая функция для чисел Каталана равна <tex>Gf(zx)=\fracdfrac{1-6z+11z^2-5z^3}\sqrt{(1-6z+8z^2)(1-z)^24x}=\frac{1-6z+11z^2-5z^3}{(1-2z)(1-4z))(1-z)^22x}=\frac{1</3}{tex>. Найдем <tex>f'(1-zx)^2}+\frac{7/9}{1-z}-\frac{1/2}{1-2z}+\frac{7/18}{1-4z}</tex>.

Разложим первое слагаемое в ряд, используя [http:<tex>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}}<//www.genfunc.ru/theory/pril02/ расширенные биномиальные коэффициенты]:tex>

<tex>g(x) = \fracdfrac{1- 2x - \sqrt{1-4x}}{(2x \sqrt{1-z)^24x}}=(+ \dfrac{1-z)^\sqrt{1-24x}}{2x}=\sum_dfrac{n=01}^{\infty} sqrt{1 -2\choose n4x}}(-z)^n=</tex>

== Приложения ===== Примеры простых производящих функций ===<tex!--easy биномы увеличить, но так имхо лучше--->На последнем шаге приведения производящей функции к замкнутому виду требуется разложить полученные слагаемые в ряд. Для этого можно воспользоваться таблицей основных производящих функций <ref>G(z)=\frac{1[http://3}{(1-z)^2}+\frac{7www.genfunc.ru/9}{1-z}-\frac{1theory/2}{1-2z}+\frac{7pril03/18}{1-4z}=Таблица производящих функций]</texref>.

<tex>=\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</tex>

<tex>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}Примечания ==<references/tex>

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

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