Изменения

'''Производя́щая фу́нкция Производящая функция''' (англ. ''generating function)''' ) — это формальный степенной ряд:

* Решения задачи подсчета объектов в комбинаторике. Например, в доказательстве [[Нахождение количества разбиений числа на слагаемые|пентагональной теоремы]] или в задаче нахождения количества расстановок <tex>m </tex> ладей на доске <tex>n</tex>&nbsp;×&nbsp;<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 \frac{1}{1-x^n}</tex> {{---}} производящая функция для последовательности <tex>p_n</tex>, где <tex>p_i</tex> {{---}} количество разбиений числа <tex>i </tex> на слагаемые.

Существует целый класс последовательностей, задаваемых рекуррентным соотношением, например, <tex>f_n</tex> {{---}} числа Фибоначчи или <tex>C_n</tex> {{---}} числа Каталана. Метод производящих функций позволяет получить выражение для <tex>a_n</tex> через номер элемента в последовательности в замкнутом виде, то есть в таком виде, что выражение можно вычислить, предполагая, что <tex>z </tex> достаточно мало.

Пусть последовательность <tex>(a_0, a_1, a_2, ...)</tex> удовлетворяет некоторому рекуррентному соотношению. Мы хотим получить выражение для <tex>a_n</tex> (при <tex>n \ge geqslant 0</tex>) в замкнутом виде. Алгоритм получения замкнутого выражения для чисел <tex>a_n</tex>, удовлетворяющих рекуррентному соотношению, с помощью производящих функций состоит из 4 шагов:

# Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен <tex>k</tex>, то есть количество предшествующих элементов, требуемых для вычисления элемента с номером <tex>n</tex>, равно <tex>k</tex>):

#: <tex>a_{n}=..., n \ge geqslant k.</tex># Домножить каждую строчку на <tex>z </tex> в соответствующей степени и просуммировать строчки для всех n <tex> n \ge geqslant 0 </tex>.

<tex>a_n=6a_{n-1}-8a_{n-2}+n, n \ge geqslant 2</tex>

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

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

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

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

| <tex>(1, 0, 0,...)</tex> || <tex>1 </tex> || <tex>1</tex>

| <tex>(0, 0, ..., 0, 1, 0, 0...)</tex> (<tex>m </tex> нулей в начале) || <tex>z^m</tex> || <tex>z^m</tex>

== Ссылки Примечания ==<references/> == Источники информации ==