Изменения

Перейти к: навигация, поиск

Производящая функция

5 байт добавлено, 19:12, 4 января 2017
Нет описания правки
Производящая функция используется для:
* Компактной записи информации о последовательности;.* Нахождения зависимости <tex>a_n(n)</tex> для последовательности <tex>a_n</tex>, заданной рекуррентным соотношением. Например, для чисел Фибоначчи;.* Нахождения рекуррентного соотношения для последовательности {{---}} вид производящей функции может помочь найти формулу;.* Исследования асимптотического поведения последовательности;.* Доказательства тождеств с последовательностями;.* Решения задачи подсчета объектов в комбинаторике.Например, в доказательстве[[Нахождение количества разбиений числа на слагаемые|пентагональной теоремы]] или в задаче нахождения количества расстановок <tex>m</tex> ладей на доске <tex>n</tex>&nbsp;×&nbsp;<tex>n</tex>;.
* Вычисления бесконечных сумм.
 
== Примеры производящих функций ==
Рассмотрим производящие функции для различных комбинаторных последовательностей:
* <tex>\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> \prod_{n=1}^\infty \dfrac{1}{1-x^n}</tex> {{---}} производящая функция для последовательности <tex>p_n</tex>, где <tex>p_i</tex>{{---}}количество число разбиений числа <tex>i</tex> на слагаемые.
* <tex>\prod_{ n = 1}^\infty(1+x^n)</tex> {{---}} производящая функция для последовательности <tex>d_n</tex>, где <tex>d_i</tex>{{---}}количество число разбиений на различные слагаемые.
* <tex>\prod_{n=1}^\infty(1+x^{ 2n - 1})</tex> {{---}} производящая функция для последовательности <tex>l_n</tex>, где <tex>l_i</tex>{{---}}количество число разбиений на нечётные слагаемые.С помощью метода производящих функций можно доказать, что производящие функции последовательностей равны, соответственно <tex>d_n = l_n </tex>: <tex>\prod_{n=1}^\infty(1+x^{ n})=\prod_{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>
|+
|-align="center" bgcolor=#EEEEFF
| '''Последовательность ''' || '''Производящая функция в виде ряда ''' || '''Производящая функция в замкнутом виде'''
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 0, 0,\ldots)</tex> || <tex>1</tex> || <tex>1</tex>
| <tex>(1, 1, \dfrac{1}{2}, \dfrac{1}{6}, \dfrac{1}{24},\ldots)</tex> || <tex>\sum \dfrac{1}{n!}</tex> <tex>z^n</tex> || <tex>e^z</tex>
|}
 
== См. также ==
== Примечания ==
30
правок

Навигация