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

Материал из Википедии — свободной энциклопедии

В комбинаторике производя́щая фу́нкция последовательности ${a n}$ — это формальный степенной ряд

$\sum_{n=0}^\infty a_n x^n$ .

Экспоненциальная производящая функция последовательности ${a n}$ — это формальный степенной ряд

$\sum_{n=0}^\infty a_n \frac{x^n}{n!}$ .

Довольно часто производящая функция интересующей последовательности ${a n}$ является рядом Тейлора известной аналитической функции, и это может использоваться для изучения свойств самой последовательности. Тем не менее, следует отметить, что производящей функции не обязана соответствовать аналитическая функция.

Например, оба ряда

$\sum_{n=0}^\infty (3^n)^n x^n$ и $\sum_{n=0}^\infty (2^n)^n x^n$

имеют радиус сходимости ноль, т.е. расходятся во всех точках, кроме нуля, а в нуле оба дают 1, т.е. как функции они совпадают; тем не менее, как производящие функции (т.е. формальные ряды) они различны.

Производящие функции дают возможность просто описывать многие сложные последовательности в комбинаторике, а иногда помогают найти для них явные формулы. Метод производящих функций был разработан Эйлером в 50-х годах XVIII века.

[править] Свойства

(Экспоненциальная) производящая функция суммы (или разности) двух последовательностей равна сумме (или разности) соответствующих (экспоненциальных) производящих функций.
Если $A(x)=\sum_{n=0}^\infty a_n x^n$ и $B(x)=\sum_{n=0}^\infty b_n x^n$ — производящие функции последовательностей ${a n}$ и ${b n}$ , то $A(x)B(x)=\sum_{n=0}^\infty c_n x^n$ , где $c_n = \sum_{k=0}^n a_k b_{n-k}$ .
Если $A(x)=\sum_{n=0}^\infty a_n \frac{x^n}{n!}$ и $B(x)=\sum_{n=0}^\infty b_n \frac{x^n}{n!}$ — экспоненциальные производящие функции последовательностей ${a n}$ и ${b n}$ , то $A(x)B(x)=\sum_{n=0}^\infty c_n \frac{x^n}{n!}$ , где $c_n = \sum_{k=0}^n {n\choose k} a_k b_{n-k}$ .

[править] Примеры

Пусть $B n$ есть число представлений числа $n$ в виде $k_1+k_2+\cdots+k_m$ , где ${k i}$ — неотрицательные целые числа и $m$ фиксировано, тогда

$\sum_{n=0}^\infty B_nx^n=(1+x+x^2+\cdots)^m=(1-x)^{-m}$

Теперь число $B n$ может быть найдено как коэффициент при $x n$ в разложении $(1 - x) - m$ по степеням $x$ . Для этого можно воспользоваться определением биномиальных коэффициентов или же непосредственно взять n раз производную в нуле: