31
правка
Изменения
→Пример задачи на нахождение производящей функции: Упрощение итоговой формулы
{{Определение
|id=main
|definition=
'''Производящая функция''' (англ. ''generating function'') — это формальный степенной ряд:<center>вида <tex>G(z)=\sum\limits_{n=0}^\infty a_n z^n</tex>,</center>порождающий(производящий) последовательность <tex>(a_0, a_1, a_2, \ldots)</tex>.
}}
Метод производящих функций был разработан Эйлером в 1750-х годах.
* Исследования асимптотического поведения последовательности.
* Доказательства тождеств с последовательностями.
* Решения задачи подсчета объектов в комбинаторике.Например, в доказательстве[[Нахождение количества разбиений числа на слагаемые|пентагональной теоремы]] или в задаче нахождения количества расстановок <tex>m</tex> ладей на доске <tex>n</tex> × <tex>\times n</tex>.
* Вычисления бесконечных сумм.
Рассмотрим производящие функции для различных комбинаторных последовательностей:
* <tex>\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>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>\dfrac{ 1}{(1-z)^2}=(1-z)^{-2}=\sum\limits_{n=0}^{\infty} {-2\choose n}(-z)^n=</tex> <tex>=\sum\limits_{n=0}^{\infty} (-1)^n{n+1\choose 1}(-z)^n=\sum\limits_{n=0}^{\infty}(n+1)z^n</tex>
<tex>G(z)=\dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}=\dfrac{1}{3}\sum\limits_{n=0}^{\infty} (n+1)z^n +\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>\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}</tex>
=== Пример задачи на нахождение производящей функции ===
{{Задача
| about =
| definition = Рассмотрим множество путей на прямой, состоящих из шагов длины <tex>1</tex> вправо и влево. Найдите производящую функцию для числа таких путей из <tex>n</tex> шагов, начинающихся в <tex>0</tex> и оканчивающихся в <tex>0</tex>.
}}
Заметим, что для того, чтобы закончить путь в <tex>0</tex>, необходимо совершить равное число шагов вправо и влево. Тогда задача сводится к тому, чтобы выбрать <tex>\dfrac{n}{2}</tex> позиций для, например, шагов вправо из всего <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>, где <tex>C_n</tex> {{---}} [[Числа Каталана | число Каталана]]. Тогда, заметим что <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>f(x) = \dfrac{1-\sqrt{1-4x}}{2x}</tex>. Найдем <tex>f'(x)</tex>.
<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}}
</tex>
Соответственно, ответом будет производящая функция вида:
<tex>
g(x) = \dfrac{1 - 2x - \sqrt{1-4x}}{2x \sqrt{1-4x}} + \dfrac{1-\sqrt{1-4x}}{2x} = \dfrac{1}{\sqrt{1 - 4x}}
</tex>
{{Задача
| about =
| definition = Рассмотрим множество путей на прямой, состоящих из шагов длины <tex>1</tex> вправо и влево. Найдите производящую функцию для числа таких путей из <tex>n</tex> шагов, начинающихся и оканчивающихся в <tex>0</tex> и не заходящих в отрицательную полупрямую.
}}
Заметим, что задача аналогична [[Правильные скобочные последовательности | Правильной скобочной последовательности]]. Тогда производящей функцией для нашей задачи будет производящая функция для правильной скобочной последовательности, а именно:
<tex>
g(x) = \dfrac{1-\sqrt{1-4x}}{2x}
</tex>
== Приложения ==
=== Примеры простых производящих функций ===
<!--easy биномы увеличить, но так имхо лучше--->На последнем шаге приведения производящей функции к замкнутому виду требуется разложить полученные слагаемые в ряд. Для этого можно воспользоваться таблицей основных производящих функций <ref>[http://www.genfunc.ru/theory/pril03/ Таблица производящих функций]</ref>.
Все суммы выполняются по переменной <tex>n</tex> от <tex>0</tex> до <tex>\infty</tex>. Элементы последовательности нумеруются от <tex>0</tex>.
| <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)^2}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, r, r^2, r^3,\ldots)</tex> || <tex>\sum\limits r^nz^n</tex> || <tex>\dfrac{1}{(1-rz)^2}</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\choose n}</tex> <tex>z^n</tex> || <tex>(1+z)^m</tex>
| <tex>(m, -\dfrac{1}{3!}m^3, \dfrac{1}{5!}m^5, -\dfrac{1}{7!}m^7, \dfrac{1}{9!}m^9,\ldots)</tex> || <tex>\sum\limits \dfrac{1}{(2n-1)!}</tex> <tex>m^{(2n-1)}</tex> || <tex>\sin m</tex>
|}
== См. также ==
* [[Производящая функция Дирихле]]
== Примечания ==
