88
правок
Изменения
Нет описания правки
|definition=
'''Производя́щая фу́нкция (generating function)''' — это формальный степенной ряд:
<tex>G(z)=\sum_{n=0}^\infty a_n z^n</tex>.,порождающий (производящий) последовательность <tex>(a_0, a_1, a_2, ...)</tex>.
}}
== Применение ==
Производящая функция используется:
* Нахождение зависимости <tex>a_n(n)</tex> для последовательности <tex>a_n</tex>, заданной рекурентным рекуррентным соотношением. Например для чисел Фибоначчи.
* Исследование асимптотического поведения последовательности.
* Доказательство тождеств с последовательностями
<tex>G(z)=a_0+a_1z+6z(G(z)-a_0) - 8z^2G(z)z^n+\sum_{n=2}^\infty n z^n</tex>
<tex>G(z)=1-4z+6zG(z) - 8z^2G(z)z^n+\sum_{n=2}^\infty n z^n</tex>
<tex>z (\frac{z^2}{1-z})'=\frac{z^2(2-z)}{(1-z)^2}</tex>
Таким образом наше последнее слагаемое примет вид:
<tex>G(z)=1-4z+6zG(z) - 8z^2G(z)+\frac{z^2(2-z)}{(1-z)^2}</tex>
Это уравнение для производящей функции. Из него выражаем <tex>G(z)</tex>:
<tex>G(z)=\frac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}</tex>
