31
правка
Изменения
→Пример задачи на нахождение производящей функции: Упрощение итоговой формулы
{{Определение
|id=main
|definition=
'''Производя́щая фу́нкция Производящая функция''' (англ. ''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>.
}}
Метод производящих функций был разработан Эйлером в 1750-х годах.
Производящая функция используется для:
* Компактной записи информации о последовательности;.* Нахождения зависимости <tex>a_n(n)</tex> для последовательности <tex>a_n</tex>, заданной рекуррентным соотношением. Например, для чисел Фибоначчи;.* Нахождения рекуррентного соотношения для последовательности {{---}} вид производящей функции может помочь найти формулу;.* Исследования асимптотического поведения последовательности;.* Доказательства тождеств с последовательностями;.* Решения задачи подсчета объектов в комбинаторике. Например, в доказательстве [[Нахождение количества разбиений числа на слагаемые|пентагональной теоремы]] или в задаче нахождения количества расстановок <tex>m </tex> ладей на доске <tex>n × \times n;</tex>.* Вычисления бесконечных сумм.
== Примеры производящих функций ==
Рассмотрим производящие функции для различных комбинаторных последовательностей:
* <tex dpi = "180">\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 dpi = "180"> \prod_prod\limits_{n=1}^\infty \fracdfrac{1}{1-x^n}</tex> {{---}} производящая функция для последовательности <tex>p_n</tex>, где <tex>p_i</tex> {{---}} количество число разбиений числа <tex>i </tex> на слагаемые.
* <tex dpi = "180">\prod_prod\limits_{n=1}^\infty (1+x^n)</tex> {{---}} производящая функция для последовательности <tex>d_n</tex>, где <tex>d_i</tex> {{---}} количество число разбиений на различные слагаемые.
* <tex dpi = "180">\prod_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 dpi = "180"> \prod_prod\limits_{n=1}^\infty (1+x^{n})=\prod_prod\limits_{n=1}^\infty \fracdfrac{1-x^{2n}}{1-x^n}=\fracdfrac{1-x^2}{1-x}\fracdfrac{1-x^4}{1-x^2}\fracdfrac{1-x^6}{1-x^3}...\ldots=</tex>
<tex dpi = "180">=\fracdfrac{1}{1-x}\fracdfrac{1}{1-x^3}\fracdfrac{1}{1-x^5}...\ldots=\prod_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 \ge geqslant 0</tex>) в замкнутом виде. Алгоритм получения замкнутого выражения для чисел <tex>a_n</tex>, удовлетворяющих рекуррентному соотношению, с помощью производящих функций состоит из 4 шагов:
<tex>a_1a_0=...1,</tex>
<tex>a_{k-1}a_1=...2,</tex>
<tex>a_a_n= 6a_{ n - 1}-8a_{n-2}=...+n, n \ge k.geqslant 2</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>a_nG(z)=6a_{na_0+a_1z+6z(G(z)-1}a_0) -8a_8z^2G(z)+\sum\limits_{n-=2}+^\infty n, z^n \ge 2</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>:
Разложим первое слагаемое в ряд, используя расширенные биномиальные коэффициенты <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>
* <tex dpi = "180">G(z)=\fracoperatorname{1-6z+11z^2-5z^3E}{(1-6z+8z^2\xi)(1-z)^2}=\fracsum\limits_{n=1-6z+11z^2-5z}^3}{(1-2z)(1-4z)(1-z)^2}=\frac{1/3infty}{n p(1-zp)^2}+\frac{7/9}{1-z}-\frac{1/2}{1n-2z}+\frac{7/18}{1-4z}</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 dpi = "160">G(z)=\fracsum\limits_{1/3n=0}^{\infty}(n+1) p(1-zp)^2}+\frac{7/9}{1-z}-\frac{1/2}{1-2z}+\frac{7/18}{1-4zn}=</tex>
<tex>= \sum\limits_{n=0}^{\infty}n p(1-p)^{n} + \sum\limits_{n=1}^{\infty} p(1-p)^{n-1} = </tex>
<tex dpi = "160">=\frac{(1}{3}-p) \sum_operatorname{n=0E}^{(\infty} (nxi) +1)z^n +\fracRightarrow \operatorname{7}{9E}(\sum_{nxi) =0}^{\infty} z^n - \fracdfrac{1}{2}\sum_{n=0}^{\infty} 2^n z^n + \frac{7}{18}\sum_{n=0}^{\inftyp} 4^n z^n</tex>
* <tex dpi = "160">a_n=\frac{n+1}operatorname{3E}+(\frac{7}{9}-\frac{2xi^n}{2}+) = p\sum\fraclimits_{7 \cdot 4^n=1}^{18\infty}=\frac{7 \cdot 4n^n+6n+20}{182}(1-2p)^{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(\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\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>
Мы знаем, что производящая функция для чисел Каталана равна <tex dpi = "160">f(x) = \sum_dfrac{1-\sqrt{n=01-4x}}^{\infty2x}</tex>. Найдем <tex>f'(n+1x) p (1-p)^{n} = </tex>.
<tex dpi = "160">f'(x) = \sum_dfrac{\dfrac{n=04x}^{\infty}n p (sqrt{1-p)^{n4x}} - 2 + 2\sum_sqrt{n=1-4x}}{4x^2} = \dfrac{1 - 2x - \infty} p (sqrt{1-p)4x}}{2x^2 \sqrt{n1-14x}} = </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>
<tex dpi = "160"> g(x) = p\frac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\frac{1}dfrac{1-(1-p)} \cdot (sqrt{1-p)^2\right) +p\frac{\operatorname{d}}{\operatorname{d4x}p}\left(\frac{12x}{1-(1-p)}\cdot(1-p)\right) =</tex>
Все суммы выполняются по переменной <tex dpi >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= "160left"bgcolor=#FFFFFF| <tex>(1, 1, 1,\ldots)</tex> || <tex>\sum\limits z^n</tex> || <tex>\dfrac{1}{1-z}</tex>|-align= p"left" bgcolor=#FFFFFF| <tex>(1, 0, 0, \cdotldots, 0, 1, 0, 0, \fracldots 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}{p(1-z)^32} </tex>|- palign="left" bgcolor=#FFFFFF| <tex>(1, 2, 4, 8, 16,\ldots)</tex> || <tex>\sum\cdotlimits 2^nz^n</tex> || <tex>\fracdfrac{1}{p(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\fracchoose 0}, {m\choose 1}, {m\choose 2}, {m\choose 3},\ldots</tex><tex>)</tex> || <tex>\sum\limits {pm\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}\fracchoose n}</tex> <tex>z^n</tex> || <tex>\dfrac{1}{p(1-z)^m} </tex>|-align="left" bgcolor= #FFFFFF| <tex>(</tex><tex>1, {{m+1}\fracchoose 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>|-palign="left" bgcolor=#FFFFFF| <tex>(1, 1, \dfrac{1}{2}, \dfrac{1}{6}, \dfrac{p1}{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/ genfunc.ruПроизводящие функции]* [http://en.wikipedia.org/wiki/Generating_function Wikipedia {{--- }} Generating function]
* [[Нахождение количества разбиений числа на слагаемые|Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
* Graham, Knuth, and Patashnik: Concrete Mathematics
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Подсчёт числа объектов]]