5
правок
Изменения
Новая страница: «{{Определение |id=main |definition= '''Производящая функция''' (англ. ''generating function'') — это формальный…»
{{Определение
|id=main
|definition=
'''Производящая функция''' (англ. ''generating function'') — это формальный степенной ряд вида <tex>G(z)=\sum\limits_{n=0}^\infty a_n z^n</tex>, порождающий (производящий) последовательность <tex>(a_0, a_1, a_2, \ldots)</tex>.
}}
Метод производящих функций был разработан Эйлером в 1750-х годах.
__TOC__
== Применение ==
Производящая функция используется для:
* Компактной записи информации о последовательности.
* Нахождения зависимости <tex>a_n(n)</tex> для последовательности <tex>a_n</tex>, заданной рекуррентным соотношением. Например, для чисел Фибоначчи.
* Нахождения рекуррентного соотношения для последовательности {{---}} вид производящей функции может помочь найти формулу.
* Исследования асимптотического поведения последовательности.
* Доказательства тождеств с последовательностями.
* Решения задачи подсчета объектов в комбинаторике. Например, в доказательстве [[Нахождение количества разбиений числа на слагаемые|пентагональной теоремы]] или в задаче нахождения количества расстановок <tex>m</tex> ладей на доске <tex>n \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>k</tex> увеличивает каждый производимый ей элемент в <tex>k</tex> раз:
<tex>\langle1, 0, 1, 0, 1, 0,...\rangle \xleftrightarrow{} 1 + x^2 + x ^4 + x^6 + ... = \frac{1}{1-x^2}</tex>
Умножение производящей функции на <tex>2</tex> даёт
<tex>\frac{2}{1 - x^2} = 2 + 2x^2 + 2x^4 + 2x^6 + ...</tex>
что производит следующую последовательность:
<tex>\langle2,0,2,0,2,0,...\rangle</tex>
Если <tex>\langle f_0,f_1,f_2,...\rangle \xleftrightarrow{} F(x), \text{тогда} \langle cf_0,cf_1,cf_2,...\rangle \xleftrightarrow{} c \cdot F(x)</tex>
=== Сложение производящих функций ===
Сложение производящих функций <tex>A \text{ и } B</tex> соответствует производящей функции <tex>C</tex>, такой что <tex>c_n = a_n + b_n</tex>
<tex>\langle f_0,f_1,f_2,... \xleftrightarrow{} F(x)</tex>
<tex>+ \langle g_0,g_1,g_2,... \rangle \xleftrightarrow{} G(x)</tex>
<tex>= \langle f_0+g_0,f_1+g_1,f_2+g_2,... \rangle \xleftrightarrow{} F(x) + G(x)</tex>
=== Сдвиг вправо ===
Пусть у нас есть производящая функция <tex>\langle 1,1,1,1,... \rangle \xleftrightarrow{} \frac{1}{1-x}</tex>
Мы можем сдвинуть её вправо, добавив <tex>k</tex> ведущих нулей:
<tex>\langle 0,0,...,0,1,1,1,... \rangle \xleftrightarrow{} x^k + x^{k+1} + x^{k+2} + x^{k+3} + ... = x^k \cdot (1 + x + x^2 + x^3 + ...) = \frac{x^k}{1-x}</tex>
То есть чтобы сдвинуть производящую функцию на <tex>k</tex> элементов в право, нужно умножить её на <tex>x^k</tex>
=== Дифференцирование производящей функции ===
Дифференцирование проиводящей функции сдвигае её элементы влево на одни элемент и умножает каждый элемент на его индекс:
<tex>\frac{d}{dx}(1 + x + x^2 + x^3+x^4 + ...) = \frac{d}{dx}\big(\frac{1}{1-x}\big)</tex>
<tex>\frac{d}{dx} + x\frac{d}{dx} + x^2 \frac{d}{dx} + x^3 \frac{d}{dx} + x^4 \frac{d}{dx} + ... = \frac{d}{dx}\big(\frac{1}{1-x}\big)</tex>
<tex>1 + 2x + 3x^2 + 4x^3 + ... = \frac{1}{(1-x)^2}</tex>
<tex>\langle 1,2,3,4,... \rangle \xleftrightarrow{} \frac{1}{(1-x)^2}</tex>
{{Задача
| about =
| definition = Найти производящую функцию для последовательности квадратов <tex>\langle 0,1,4,9,16,... \rangle</tex>
}}
Мы можем взять последовательность <tex>\langle 1,1,1,1,...\rangle</tex>,
давайте два раза продиффиренцируем производящую функцию для этой последовательности, чтобы получить желаемый результат. Проблема в том, что дифференцирование производит сдвиг в лeво, и в результате мы получим:
<tex>\frac{d}{dx}\frac{d}{dx}\langle 1,1,1,1,...\rangle = \langle4,9,16,...\rangle</tex>
Чтобы избежать потери первых двух элементов последовательности, мы можем применять сдвиг вправо после каждого дифференцирования:
<tex>\langle 1,1,1,1,...\rangle \xleftrightarrow{} \frac{1}{1-x}</tex>
<tex>\langle 1,2,3,4,...\rangle \xleftrightarrow{} \frac{d}{dx}\frac{1}{1-x} = \frac{1}{(1-x)^2} </tex>
<tex>\langle 0,1,2,3,...\rangle \xleftrightarrow{} x \cdot \frac{1}{(1-x)^2} = \frac{x}{(1-x)^2}</tex>
<tex>\langle 1,4,9,16,...\rangle \xleftrightarrow{} \frac{d}{dx}\frac{x}{(1-x)^2} = \frac{1+x}{(1-x)^3} </tex>
<tex>\langle 0,1,4,9,...\rangle \xleftrightarrow{} x \cdot \frac{1+x}{(1-x)^3} = \frac{x(1+x)}{(1-x)^3}</tex>
=== Произведение производящих функций ===
{{Утверждение
|statement = Пусть <tex>A \text{ и } B</tex> - классы
объектов, и <tex>A(x) \text{ и } B(x)</tex> - их производящие функции. Тогда классу <tex>C = A \times B \text{ соответствует производящая функция } C(x) = A(x)B(x).</tex>
|proof = Пусть <tex>c_n</tex> - число объектов размера <tex>n</tex> в декартовом произведении <tex>C = A \times B </tex>. Эти объекты полученны выбором объекта <tex>a \in A \text{ размера } k \leq n \text{ и объекта } b \in B \text{ размера } n-k</tex>.
Таким образом
<tex>c_n = \displaystyle\sum_{k = 0}^{n} a_k b_{n-k}.</tex>
Рассмотрим произведение производящих функций
<tex>A(x)B(x) = \Bigg(\displaystyle\sum_{k \geq 0}^{} a_k x^k\Bigg) \times \Bigg(\displaystyle\sum_{k \geq 0}^{} b_k x^k \Bigg).</tex>
<tex>A(x)B(x) = \displaystyle\sum_{n \geq 0}^{} \Bigg(\displaystyle\sum_{k \geq 0}^{n} a_k b_{n-k}\Bigg)x^n</tex>
}}
{{Задача
| about =
| definition = Дана шестигранная игральная кость, грани которой пронумерованный от <tex>1 \text{ до } 6</tex> и восьмигранная игральная кость, грани которой пронумерованны от <tex>1 \text{ до } 8</tex>. Мы кидаем кости и получаем сумму чисел, которые выпали на костях. Нужно найти число способов получить каждую сумму.
}}
Представим производящую функцию <tex>C(x) = \displaystyle_{n \geq 0}^{} c_n x^n</tex> как:
<tex>C(x) = (x+ x^2 + x^3 + x^4 + x^5 + x^6) \times (x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8)</tex>
первая часть учитывает все возможные исходы первой кости, а вторая часть учитывает исходы второй кости. Например, сумму <tex>5</tex> можно разбить на <tex>2</tex> с первой кости и <tex>3</tex> со второй. Такой исход учитывается умножением <tex>x^2</tex> из первой последовательности на <tex>x^3</tex> из второй.
<tex>C(x) = x^2 + 2x^3 + 3x^4 + 4x^5 + 5x^6 + 6x^7 + 6x^8 + 6x^9 + 5x^{10} + 4x^{11} + 3x^{12} + 2x^{13} + x^{14}</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>
Запишем производящую функцию для этой последовательности и преобразуем правую часть:
<tex>G(z)=a_0+a_1z+\sum\limits_{n=2}^\infty(6a_{ n - 1}-8a_{n-2}+n) z^n</tex>
<tex>G(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+\sum\limits_{n=2}^\infty n z^n</tex>
<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>b_n= (1, 1, 1, \ldots)</tex>). Такая последовательность получается путём дифференцирования функции <tex>B(z)</tex>, производящей для <tex>b_n</tex>, с последующим умножением результата на <tex>z</tex>:
<tex>zB'(z)=z(\sum\limits_{n=0}^\infty b_n z^n)'=z\sum\limits_{ n = 1}^\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>G(z)</tex>:
<tex>G(z)=\dfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}</tex>
Разложим знаменатель на множители и разобьём дробь на сумму простых дробей <ref>[http://www.genfunc.ru/theory/pril04/ О разложении рациональной функции в ряд]</ref>:
<tex> G(z) =\dfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}=\dfrac{1-6z+11z^2-5z^3}{(1-2z)(1-4z)(1-z)^2}=\dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}</tex>
Разложим первое слагаемое в ряд, используя расширенные биномиальные коэффициенты <ref>[http://www.genfunc.ru/theory/pril02/ Расширенные биномиальные коэффициенты]</ref>:
<tex>\dfrac{ 1}{(1-z)^2}=(1-z)^{-2}=\sum\limits_{n=0}^{\infty} {-2\choose n}(-z)^n=\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>a_n=\dfrac{n+1}{3}+\dfrac{7}{9}-\dfrac{2^n}{2}+\dfrac{7 \cdot 4^n}{18}=\dfrac{7 \cdot 4^n+6n+20}{18}-2^{n-1}</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>\operatorname{D}(\xi)=\operatorname{E}(\xi^2)-(\operatorname{E}(\xi))^2</tex> нужно найти два мат. ожидания:
* <tex>\operatorname{E}(\xi)=\sum\limits_{n=1}^{\infty}n p(1-p)^{n-1} </tex>
* <tex>\operatorname{E}(\xi^2) = \sum\limits_{n=1}^{\infty}n^{2}p(1-p)^{n-1}</tex>
которые фактически являются производящими функциями последовательностей <tex>1, 2, 3\ldots</tex> и <tex>1, 4, 9\ldots</tex>:
* <tex>\operatorname{ E}(\xi)=\sum\limits_{n=1}^{\infty}n p(1-p)^{n-1} = </tex>
<tex>= \sum\limits_{n=0}^{\infty}(n+1) p(1-p)^{n} = </tex>
<tex>= \sum\limits_{n=0}^{\infty}n p(1-p)^{n} + \sum\limits_{n=1}^{\infty} p(1-p)^{n-1} = </tex>
<tex>= (1-p) \operatorname{E}(\xi) +1 \Rightarrow \operatorname{E}(\xi) = \dfrac{1}{p}</tex>
* <tex>\operatorname{E}(\xi^2) = p\sum\limits_{n=1}^{\infty}n^{2}(1-p)^{n-1} =</tex>
<tex>=p\sum\limits_{n=1}^{\infty}n(n+1)(1-p)^{n-1} - p\sum\limits_{n=1}^{\infty}n(1-p)^{n-1} =</tex>
<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\sum\limits_{n=1}^{\infty}(1-p)^{n+1} + p\dfrac{\operatorname{d}}{\operatorname{d}p}\sum\limits_{n=1}^{\infty}(1-p)^{n} =</tex>
<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\sum\limits_{ n = 0}^{\infty}(1-p)^{n} \cdot(1-p)^2\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\sum\limits_{ n = 0}^{\infty}(1-p)^{n}\cdot(1-p)\right) =</tex>
<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\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>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\dfrac{ (1 - p) ^ 2}{p}\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\dfrac{ 1 - p}{p}\right) =</tex>
<tex>= p\cdot\dfrac{2}{p^3} - p\cdot\dfrac{1}{p^2} = \dfrac{2}{p^{2}} - \dfrac{1}{p} = \dfrac{2-p}{p^{2}}</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}
</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>.
{| class="wikitable" style="width:30cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
| '''Последовательность''' || '''Производящая функция в виде ряда''' || '''Производящая функция в замкнутом виде'''
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 0, 0,\ldots)</tex> || <tex>1</tex> || <tex>1</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(0, 0, \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>\dfrac{1}{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^{nm}</tex> || <tex>\dfrac{1}{1-z^m}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, -1, 1, -1,\ldots)</tex> || <tex>\sum\limits (-1)^nz^n</tex> || <tex>\dfrac{1}{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,\ldots)</tex> || <tex>\sum\limits r^nz^n</tex> || <tex>\dfrac{1}{(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\choose n}</tex> <tex>z^n</tex> || <tex>(1+z)^m</tex>
|-align="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}\choose n}</tex> <tex>z^n</tex> || <tex>\dfrac{1}{(1-z)^m}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(</tex><tex>1, {{m+1}\choose m}, {{m+2}\choose m}, {{m+3}\choose m},\ldots</tex><tex>)</tex> || <tex>\sum\limits {{m+n}\choose n}</tex> <tex>z^n</tex> || <tex>\dfrac{1}{(1-z)^{m+1}}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(0, 1, -\dfrac{1}{2}, \dfrac{1}{3}, -\dfrac{1}{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, \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="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 \dfrac{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, -\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>
|}
== См. также ==
* [[Производящая функция Дирихле]]
== Примечания ==
<references/>
== Источники информации ==
* [http://kvant.mirror1.mccme.ru/1988/11/razbienie_chisel.htm Вайнштейн Ф., Разбиение чисел. Журнал "Квант" № 11, 1988 год]
* [http://www.genfunc.ru/ Производящие функции]
* [http://en.wikipedia.org/wiki/Generating_function Wikipedia {{---}} Generating function]
* [[Нахождение количества разбиений числа на слагаемые|Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
* Graham, Knuth, and Patashnik: Concrete Mathematics
* [https://math.mit.edu/~goemans/18310S15/generating-function-notes.pdf generation-function-notes]
* [http://www.math.cmu.edu/~lohp/docs/math/2011-228/mit-ocw-generating-func.pdf mit-ocw-generating-func]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Подсчёт числа объектов]]
|id=main
|definition=
'''Производящая функция''' (англ. ''generating function'') — это формальный степенной ряд вида <tex>G(z)=\sum\limits_{n=0}^\infty a_n z^n</tex>, порождающий (производящий) последовательность <tex>(a_0, a_1, a_2, \ldots)</tex>.
}}
Метод производящих функций был разработан Эйлером в 1750-х годах.
__TOC__
== Применение ==
Производящая функция используется для:
* Компактной записи информации о последовательности.
* Нахождения зависимости <tex>a_n(n)</tex> для последовательности <tex>a_n</tex>, заданной рекуррентным соотношением. Например, для чисел Фибоначчи.
* Нахождения рекуррентного соотношения для последовательности {{---}} вид производящей функции может помочь найти формулу.
* Исследования асимптотического поведения последовательности.
* Доказательства тождеств с последовательностями.
* Решения задачи подсчета объектов в комбинаторике. Например, в доказательстве [[Нахождение количества разбиений числа на слагаемые|пентагональной теоремы]] или в задаче нахождения количества расстановок <tex>m</tex> ладей на доске <tex>n \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>k</tex> увеличивает каждый производимый ей элемент в <tex>k</tex> раз:
<tex>\langle1, 0, 1, 0, 1, 0,...\rangle \xleftrightarrow{} 1 + x^2 + x ^4 + x^6 + ... = \frac{1}{1-x^2}</tex>
Умножение производящей функции на <tex>2</tex> даёт
<tex>\frac{2}{1 - x^2} = 2 + 2x^2 + 2x^4 + 2x^6 + ...</tex>
что производит следующую последовательность:
<tex>\langle2,0,2,0,2,0,...\rangle</tex>
Если <tex>\langle f_0,f_1,f_2,...\rangle \xleftrightarrow{} F(x), \text{тогда} \langle cf_0,cf_1,cf_2,...\rangle \xleftrightarrow{} c \cdot F(x)</tex>
=== Сложение производящих функций ===
Сложение производящих функций <tex>A \text{ и } B</tex> соответствует производящей функции <tex>C</tex>, такой что <tex>c_n = a_n + b_n</tex>
<tex>\langle f_0,f_1,f_2,... \xleftrightarrow{} F(x)</tex>
<tex>+ \langle g_0,g_1,g_2,... \rangle \xleftrightarrow{} G(x)</tex>
<tex>= \langle f_0+g_0,f_1+g_1,f_2+g_2,... \rangle \xleftrightarrow{} F(x) + G(x)</tex>
=== Сдвиг вправо ===
Пусть у нас есть производящая функция <tex>\langle 1,1,1,1,... \rangle \xleftrightarrow{} \frac{1}{1-x}</tex>
Мы можем сдвинуть её вправо, добавив <tex>k</tex> ведущих нулей:
<tex>\langle 0,0,...,0,1,1,1,... \rangle \xleftrightarrow{} x^k + x^{k+1} + x^{k+2} + x^{k+3} + ... = x^k \cdot (1 + x + x^2 + x^3 + ...) = \frac{x^k}{1-x}</tex>
То есть чтобы сдвинуть производящую функцию на <tex>k</tex> элементов в право, нужно умножить её на <tex>x^k</tex>
=== Дифференцирование производящей функции ===
Дифференцирование проиводящей функции сдвигае её элементы влево на одни элемент и умножает каждый элемент на его индекс:
<tex>\frac{d}{dx}(1 + x + x^2 + x^3+x^4 + ...) = \frac{d}{dx}\big(\frac{1}{1-x}\big)</tex>
<tex>\frac{d}{dx} + x\frac{d}{dx} + x^2 \frac{d}{dx} + x^3 \frac{d}{dx} + x^4 \frac{d}{dx} + ... = \frac{d}{dx}\big(\frac{1}{1-x}\big)</tex>
<tex>1 + 2x + 3x^2 + 4x^3 + ... = \frac{1}{(1-x)^2}</tex>
<tex>\langle 1,2,3,4,... \rangle \xleftrightarrow{} \frac{1}{(1-x)^2}</tex>
{{Задача
| about =
| definition = Найти производящую функцию для последовательности квадратов <tex>\langle 0,1,4,9,16,... \rangle</tex>
}}
Мы можем взять последовательность <tex>\langle 1,1,1,1,...\rangle</tex>,
давайте два раза продиффиренцируем производящую функцию для этой последовательности, чтобы получить желаемый результат. Проблема в том, что дифференцирование производит сдвиг в лeво, и в результате мы получим:
<tex>\frac{d}{dx}\frac{d}{dx}\langle 1,1,1,1,...\rangle = \langle4,9,16,...\rangle</tex>
Чтобы избежать потери первых двух элементов последовательности, мы можем применять сдвиг вправо после каждого дифференцирования:
<tex>\langle 1,1,1,1,...\rangle \xleftrightarrow{} \frac{1}{1-x}</tex>
<tex>\langle 1,2,3,4,...\rangle \xleftrightarrow{} \frac{d}{dx}\frac{1}{1-x} = \frac{1}{(1-x)^2} </tex>
<tex>\langle 0,1,2,3,...\rangle \xleftrightarrow{} x \cdot \frac{1}{(1-x)^2} = \frac{x}{(1-x)^2}</tex>
<tex>\langle 1,4,9,16,...\rangle \xleftrightarrow{} \frac{d}{dx}\frac{x}{(1-x)^2} = \frac{1+x}{(1-x)^3} </tex>
<tex>\langle 0,1,4,9,...\rangle \xleftrightarrow{} x \cdot \frac{1+x}{(1-x)^3} = \frac{x(1+x)}{(1-x)^3}</tex>
=== Произведение производящих функций ===
{{Утверждение
|statement = Пусть <tex>A \text{ и } B</tex> - классы
объектов, и <tex>A(x) \text{ и } B(x)</tex> - их производящие функции. Тогда классу <tex>C = A \times B \text{ соответствует производящая функция } C(x) = A(x)B(x).</tex>
|proof = Пусть <tex>c_n</tex> - число объектов размера <tex>n</tex> в декартовом произведении <tex>C = A \times B </tex>. Эти объекты полученны выбором объекта <tex>a \in A \text{ размера } k \leq n \text{ и объекта } b \in B \text{ размера } n-k</tex>.
Таким образом
<tex>c_n = \displaystyle\sum_{k = 0}^{n} a_k b_{n-k}.</tex>
Рассмотрим произведение производящих функций
<tex>A(x)B(x) = \Bigg(\displaystyle\sum_{k \geq 0}^{} a_k x^k\Bigg) \times \Bigg(\displaystyle\sum_{k \geq 0}^{} b_k x^k \Bigg).</tex>
<tex>A(x)B(x) = \displaystyle\sum_{n \geq 0}^{} \Bigg(\displaystyle\sum_{k \geq 0}^{n} a_k b_{n-k}\Bigg)x^n</tex>
}}
{{Задача
| about =
| definition = Дана шестигранная игральная кость, грани которой пронумерованный от <tex>1 \text{ до } 6</tex> и восьмигранная игральная кость, грани которой пронумерованны от <tex>1 \text{ до } 8</tex>. Мы кидаем кости и получаем сумму чисел, которые выпали на костях. Нужно найти число способов получить каждую сумму.
}}
Представим производящую функцию <tex>C(x) = \displaystyle_{n \geq 0}^{} c_n x^n</tex> как:
<tex>C(x) = (x+ x^2 + x^3 + x^4 + x^5 + x^6) \times (x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8)</tex>
первая часть учитывает все возможные исходы первой кости, а вторая часть учитывает исходы второй кости. Например, сумму <tex>5</tex> можно разбить на <tex>2</tex> с первой кости и <tex>3</tex> со второй. Такой исход учитывается умножением <tex>x^2</tex> из первой последовательности на <tex>x^3</tex> из второй.
<tex>C(x) = x^2 + 2x^3 + 3x^4 + 4x^5 + 5x^6 + 6x^7 + 6x^8 + 6x^9 + 5x^{10} + 4x^{11} + 3x^{12} + 2x^{13} + x^{14}</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>
Запишем производящую функцию для этой последовательности и преобразуем правую часть:
<tex>G(z)=a_0+a_1z+\sum\limits_{n=2}^\infty(6a_{ n - 1}-8a_{n-2}+n) z^n</tex>
<tex>G(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+\sum\limits_{n=2}^\infty n z^n</tex>
<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>b_n= (1, 1, 1, \ldots)</tex>). Такая последовательность получается путём дифференцирования функции <tex>B(z)</tex>, производящей для <tex>b_n</tex>, с последующим умножением результата на <tex>z</tex>:
<tex>zB'(z)=z(\sum\limits_{n=0}^\infty b_n z^n)'=z\sum\limits_{ n = 1}^\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>G(z)</tex>:
<tex>G(z)=\dfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}</tex>
Разложим знаменатель на множители и разобьём дробь на сумму простых дробей <ref>[http://www.genfunc.ru/theory/pril04/ О разложении рациональной функции в ряд]</ref>:
<tex> G(z) =\dfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}=\dfrac{1-6z+11z^2-5z^3}{(1-2z)(1-4z)(1-z)^2}=\dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}</tex>
Разложим первое слагаемое в ряд, используя расширенные биномиальные коэффициенты <ref>[http://www.genfunc.ru/theory/pril02/ Расширенные биномиальные коэффициенты]</ref>:
<tex>\dfrac{ 1}{(1-z)^2}=(1-z)^{-2}=\sum\limits_{n=0}^{\infty} {-2\choose n}(-z)^n=\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>a_n=\dfrac{n+1}{3}+\dfrac{7}{9}-\dfrac{2^n}{2}+\dfrac{7 \cdot 4^n}{18}=\dfrac{7 \cdot 4^n+6n+20}{18}-2^{n-1}</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>\operatorname{D}(\xi)=\operatorname{E}(\xi^2)-(\operatorname{E}(\xi))^2</tex> нужно найти два мат. ожидания:
* <tex>\operatorname{E}(\xi)=\sum\limits_{n=1}^{\infty}n p(1-p)^{n-1} </tex>
* <tex>\operatorname{E}(\xi^2) = \sum\limits_{n=1}^{\infty}n^{2}p(1-p)^{n-1}</tex>
которые фактически являются производящими функциями последовательностей <tex>1, 2, 3\ldots</tex> и <tex>1, 4, 9\ldots</tex>:
* <tex>\operatorname{ E}(\xi)=\sum\limits_{n=1}^{\infty}n p(1-p)^{n-1} = </tex>
<tex>= \sum\limits_{n=0}^{\infty}(n+1) p(1-p)^{n} = </tex>
<tex>= \sum\limits_{n=0}^{\infty}n p(1-p)^{n} + \sum\limits_{n=1}^{\infty} p(1-p)^{n-1} = </tex>
<tex>= (1-p) \operatorname{E}(\xi) +1 \Rightarrow \operatorname{E}(\xi) = \dfrac{1}{p}</tex>
* <tex>\operatorname{E}(\xi^2) = p\sum\limits_{n=1}^{\infty}n^{2}(1-p)^{n-1} =</tex>
<tex>=p\sum\limits_{n=1}^{\infty}n(n+1)(1-p)^{n-1} - p\sum\limits_{n=1}^{\infty}n(1-p)^{n-1} =</tex>
<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\sum\limits_{n=1}^{\infty}(1-p)^{n+1} + p\dfrac{\operatorname{d}}{\operatorname{d}p}\sum\limits_{n=1}^{\infty}(1-p)^{n} =</tex>
<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\sum\limits_{ n = 0}^{\infty}(1-p)^{n} \cdot(1-p)^2\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\sum\limits_{ n = 0}^{\infty}(1-p)^{n}\cdot(1-p)\right) =</tex>
<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\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>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\dfrac{ (1 - p) ^ 2}{p}\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\dfrac{ 1 - p}{p}\right) =</tex>
<tex>= p\cdot\dfrac{2}{p^3} - p\cdot\dfrac{1}{p^2} = \dfrac{2}{p^{2}} - \dfrac{1}{p} = \dfrac{2-p}{p^{2}}</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}
</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>.
{| class="wikitable" style="width:30cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
| '''Последовательность''' || '''Производящая функция в виде ряда''' || '''Производящая функция в замкнутом виде'''
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 0, 0,\ldots)</tex> || <tex>1</tex> || <tex>1</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(0, 0, \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>\dfrac{1}{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^{nm}</tex> || <tex>\dfrac{1}{1-z^m}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, -1, 1, -1,\ldots)</tex> || <tex>\sum\limits (-1)^nz^n</tex> || <tex>\dfrac{1}{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,\ldots)</tex> || <tex>\sum\limits r^nz^n</tex> || <tex>\dfrac{1}{(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\choose n}</tex> <tex>z^n</tex> || <tex>(1+z)^m</tex>
|-align="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}\choose n}</tex> <tex>z^n</tex> || <tex>\dfrac{1}{(1-z)^m}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(</tex><tex>1, {{m+1}\choose m}, {{m+2}\choose m}, {{m+3}\choose m},\ldots</tex><tex>)</tex> || <tex>\sum\limits {{m+n}\choose n}</tex> <tex>z^n</tex> || <tex>\dfrac{1}{(1-z)^{m+1}}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(0, 1, -\dfrac{1}{2}, \dfrac{1}{3}, -\dfrac{1}{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, \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="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 \dfrac{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, -\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>
|}
== См. также ==
* [[Производящая функция Дирихле]]
== Примечания ==
<references/>
== Источники информации ==
* [http://kvant.mirror1.mccme.ru/1988/11/razbienie_chisel.htm Вайнштейн Ф., Разбиение чисел. Журнал "Квант" № 11, 1988 год]
* [http://www.genfunc.ru/ Производящие функции]
* [http://en.wikipedia.org/wiki/Generating_function Wikipedia {{---}} Generating function]
* [[Нахождение количества разбиений числа на слагаемые|Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
* Graham, Knuth, and Patashnik: Concrete Mathematics
* [https://math.mit.edu/~goemans/18310S15/generating-function-notes.pdf generation-function-notes]
* [http://www.math.cmu.edu/~lohp/docs/math/2011-228/mit-ocw-generating-func.pdf mit-ocw-generating-func]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Подсчёт числа объектов]]
