Комбинаторные алгоритмы для программистов



             

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


Пусть дана некоторая последовательность чисел

a_0,a_1,\ldots,a_n,\ldots
. Образуем степенной ряд

a_0 + a_1 x + \ldots + a_n x^n + \ldots.

Если этот ряд сходится в какой-то области к функции

f(x)
, то эту функцию называют производящей для последовательности чисел
a_0,a_1,\ldots,a_n,\ldots
Например, из формулы

\frac{1}{{1 - x}} = 1 + x + \ldots + x^n + \ldots

вытекает, что функция

\frac{1} {{1 - x}}
является производящей для последовательности чисел. А формула (10.1) показывает, что для последовательности чисел
1, 2, 3, 4, ..., n, ...

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

\frac{1} {{(1 - x)^2 }}
.

Нас будут интересовать производящие функции для последовательностей

a_0, a_1,\ldots,a_n,\ldots
, так или иначе связанных с комбинаторными задачами. С помощью таких функций удается получить самые разные свойства этих последовательностей. Кроме того, мы рассмотрим, как связаны производящие функции с решением рекуррентных соотношений.




Содержание  Назад  Вперед