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

Производящие функции и рекуррентные соотношения


Теория производящих функций тесно связана с рекуррентными соотношениями. Вернемся снова к делению многочленов. Пусть функции

и
разложены в степенные ряды,

- два многочлена, причем

. Мы будем, кроме того, предполагать, что
, то есть, что алгебраическая дробь
правильна (в противном случае мы всегда можем выделить из нее целую часть). Мы знаем, что если

(10.10)

то

Раскроем в правой части этого равенства скобки и сравним коэффициенты при одинаковых степенях

слева и справа. Сначала мы получим
соотношений такого вида:

(10.11)

(если

, то мы считаем, что
). А дальше все соотношения имеют один и тот же вид:

(10.12)

(ведь в

нет членов, содержащих
и т.д.). Таким образом, коэффициенты
ряда (10.10) удовлетворяют рекуррентному соотношению (10.12). Коэффициенты этого соотношения зависят лишь от знаменателя дроби. Числитель же дроби нужен для нахождения первых членов
рекуррентной последовательности.

Обратно, если дано рекуррентное соотношение (10.12) и заданы члены

, то мы сначала по формулам (10.11) вычислим значения
. А тогда производящей функцией для последовательности чисел
является алгебраическая дробь

(10.13)

На первый взгляд кажется, что мы мало выиграли при замене рекуррентного соотношения производящей функции. Ведь все равно придется делить числитель на знаменатель, а это приведет к тому же самому рекуррентному соотношению (10.12). Но дело в том, что над дробью (10.13) можно выполнять некоторые алгебраические преобразования, а это облегчит отыскание чисел

.



Содержание раздела



Главная сайта