Метод производящий функций

Этот метод используется для перечисления комбинаторных чисел и установления комбинаторных тождеств.

Исходным пунктом являются последовательность {a_i} комбинаторных чисел и последовательность функций {φ_i(x)} (i = 0, 1, …).

Рассмотрим ряд

,

который, в случае, когда последовательность {a_i} конечна, т.е. 0 ≤ i ≤ n, будет многочленом.

При определенных ограничениях данный ряд будет сходящимся и тогда он в некоторой области будет задавать функцию F(x):

Эта функция называется производящей функцией.

 

Пример 1.

(i=0,1, …, n), φ_i(x)-xⁱ

В этом случае имеем

В качестве производящей функции здесь будет бином Ньютона.

С помощью производящей функции установим тождество

Для этого возьмем тождество

Оно эквивалентно тождеству

Сравнивая коэффициенты при xⁿ, получим

 

Пример 1.

Применение метода производящей функции, когда функция определяется степенным рядом.

Последовательность чисел f_n называется числами Фибоначчи, задается рекуррентными соотношениями f_n = f_n-1+ f_n-2иf₀ = f₁ = 1

Возьмем φ_n(x) = xⁿ (n = 0,1, 2, …). С этой последовательностью связан ряд

который в силу f_n ≤ 2ⁿ (поскольку f_n ≤ 2f_n-1) сходится при │x│ < ½ и определяет производящую функцию F(x)

Так как

и

то

или