Изменения

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

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

6 байт добавлено, 19:34, 1 марта 2018
Примеры производящих функций
Рассмотрим производящие функции для различных комбинаторных последовательностей:
* <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(1+x^n)</tex> {{---}} производящая функция для последовательности <tex>d_n</tex>, где <tex>d_i</tex> {{---}} число разбиений на различные слагаемые.
* <tex>\prod\limits_{n=1}^\infty(1+x^{ 2n - 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>
693
правки

Навигация