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



             

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


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

f(x)
и
\varphi (x)
разложены в степенные ряды,

 f\left( x \right) = a_0 + a_1 x + \ldots a_n x^n + \ldots

\varphi (x) = b_0 + b_1 x + \ldots b_n x^n \ldots

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

b_0 \ne 0
. Мы будем, кроме того, предполагать, что
n < m
, то есть, что алгебраическая дробь
\frac{{f(x)}}{{\varphi (x)}}
правильна (в противном случае мы всегда можем выделить из нее целую часть). Мы знаем, что если

 \frac{{f(x)}} {{\varphi (x)}} = c_0 + c_{1x} x + \ldots + c_k x^k + \ldots,

(10.10)

то

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

= (b_0 + b_1 x + \ldots + b_m x^m )(c_0 + c_1 x + \ldots + c_k x^k + \ldots ).

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

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

 \begin{gathered} b_0 c_0 = a_0,\\ b_0 c_1 + b_1 c_0 = a_1,\\ b_0 c_2 + b_1 c_1 + b_2 c_0 = a_2,\\ .....................\\ b_0 c_{m - 1} + b_1 c_{m - 2} + \ldots + b_{m - 1} c_0 = a_{m - 1} \end{gathered}

(10.11)

(если

n < m - 1
, то мы считаем, что
a_{n + 1} = \ldots = a_{m - 1} = 0
). А дальше все соотношения имеют один и тот же вид:

 b_0 c_{m + k} + b_1 c_{m + k - 1} + \ldots + b_m c_k = 0 ,\quad k = 0,1\ldots.

(10.12)

(ведь в

f(x)
нет членов, содержащих
x^m,x^{m + 1}
и т.д.). Таким образом, коэффициенты
c_0,c_1,\ldots,c_k,\ldots
ряда (10.10) удовлетворяют рекуррентному соотношению (10.12). Коэффициенты этого соотношения зависят лишь от знаменателя дроби. Числитель же дроби нужен для нахождения первых членов
c_0,c_1,\ldots,c_{m-1}
рекуррентной последовательности.

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

c_0,c_1,\ldots,c_{m-1}
, то мы сначала по формулам (10.11) вычислим значения
a_0,\ldots,a_{m - 1}
. А тогда производящей функцией для последовательности чисел
c_0,c_1,\ldots,c_k,\ldots
является алгебраическая дробь

 \frac{{f(x)}} {{\varphi (x)}} = \frac{{a_0 + ax + \ldots + a_{m - 1} x^{m - 1} }} {{b_0 + b_1 x + \ldots + b_m x^m }}.

(10.13)

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

c_k
.




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