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

             

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


В комбинаторных задачах на подсчет числа объектов при наличии некоторых ограничений искомым решением часто является последовательность

a_0,a_{1,},a_2,\ldots
, где
a_k
- число искомых объектов "размерности"
k
. Например, если мы ищем число разбиений числа, то можем принять
a_k = P(k)
, если ищем число подмножеств
n
-элементного множества, то
a_k =(_k^n)
и т.д. В этом случае удобно последовательности
a_0,a_{1,},a_2,\ldots
, поставить в соответствие формальный ряд
A(x) = \sum\limits_{k = 0}^\infty {a_k x^k },

(8.12)

называемый производящей функцией для данной последовательности. Название формальный ряд для данной последовательности означает, что (8.12) мы трактуем только как удобную запись нашей последовательности - в данном случае несущественно, для каких (действительных или комплексных) значений переменной

x
он сходится. Поэтому мы никогда не будем вычислять значение такого ряда для конкретного значения переменной
x
, мы будем только выполнять некоторые операции на таких рядах, а затем определять коэффициенты при отдельных степенях переменной
x
. Для произвольных рядов
A(x) = \sum\limits_{k = 0}^\infty {a_k x^k,B(x) = \sum\limits_{k = 0}^\infty {b_k x^k } }

мы определим операцию сложения:

A(x) + B(x) = \sum\limits_{k = 0}^\infty {(a_k + b_k )x^k },

(8.13)

операцию умножения на число (действительное или комплексное):

pA(x) = \sum\limits_{k = 0}^\infty {pa_k x^k }

(8.14)

и произведение Коши

A(x) \cdot B(x) = \sum\limits_{k = 0}^\infty {c_k x^k },

(8.15)

где

 c_k = a_0 b_k + a_1^{} b_{k - 1} + \ldots + a_k b_0 = \sum\limits_{i = 0}^k {a_i b_{k - i} },

(8.16)

Если

a_k = 0
для
k > n
, то ряд (8.12) будем отождествлять с многочленом
a_n x^n + \ldots + a_0
. Из математического анализа известно, что если ряд (8.12) сходится в некоторой окрестности нуля, то его сумма
A(x)
является аналитической функцией в этой окрестности и
a_k = A^{(k)} (0)/k!,k = 0,1,2,\ldots

(8.17)

(

A^{(k)} (0)
обозначает значение
k
-й производной функции
A(x)
для
x = 0
; ряд 8.12 - это не что иное, как ряд Маклорена функции
A(x)
). Более того, когда
A(x),B(x)
являются аналитическими функциями в окрестности нуля, то формулы (8.13)-(8.16) будут справедливы, если
A(x),B(x)
трактовать как значения функций
A,B
в точке
x
, а ряды понимать в обычном смысле, т.е. так, как в математическом анализе. Это сохраняющее операции взаимно однозначное соответствие между рядами, сходящимися в окрестности нуля, и функциями, аналитическими в окрестности нуля, позволяет отождествить формальный ряд (8.12) с определенной через него аналитической функцией в случае рядов, сходящихся в окрестности нуля (несмотря на то, что ряды мы будем трактовать всегда как формальные ряды, то есть только как формальную запись их коэффициентов). Таким образом, будем писать, например,
\sum\limits_{k = 0}^\infty {x^k = (1 - x)^{ - 1} },

\sum\limits_{k = 0}^\infty {\frac{1}{{k!}}x^k = e^x }

и т.д.




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