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

         

Об едином нелинейном рекуррентном соотношении


При решении задачи о разбиении последовательности мы пришли к рекуррентному соотношению

(10.14)

где

.Покажем, как решить соотношение (10.14). Для этого составим производящую функцию.

(10.15)

Положим

(10.16)

и возведем

в квадрат. Мы получим, что

Но по рекуррентному соотношению (10.14),

Значит,

Полученный ряд есть не что иное, как

; поскольку
, он равен

Для функции

получилось квадратное уравнение (10.17). Решая его, находим, что

Мы выбрали перед корнем знак минус, так как в противном случае при

мы имели бы

, а из разложения (10.16) видно, что
.


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