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



             

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


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

 T_n = T_0 T_{n - 1} + T_1 T_{n - 2} + \ldots + T_{n - 1} T_0,

(10.14)

где

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

 f(x) = T_0 + T_1 x + T_2^{} x^2 + \ldots + T_n x^n + \ldots

(10.15)

Положим

 F(x) \equiv xf(x) = T_0 x + T_1 x^2 + \ldots + T_n x^{n + 1} + \ldots

(10.16)

и возведем

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

 F^2 (x) = T_0^2 + (T_0 T_1 + T_1 T_0 )x^3 + \ldots

...+ (T_0 T_{n - 1} + \ldots + T_{n - 1} T_0 )x^{n + 1} + \ldots

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

T_0 T_{n - 1} + \ldots + T_{n - 1} T_0 = T_n.

Значит,

F^2 (x) = T_1 x^2 + T_2 x^3 + \ldots + T_n x^{n + 1}.

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

F(x) - T_0 x
; поскольку
T_0 = 1
, он равен

F^2 (x) = F(x) - x.

Для функции

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

F(x) = \frac{{1 - \sqrt {1 - 4x} }}{2}.

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

x =0

мы имели бы

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




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