ВУЗ:
Составители:
Рубрика:
20
§ 14. Понятие о методе производящих функций
Метод производящих функций является одним из наиболее эффективных ме-
тодов решения комбинаторных задач. При использовании этого метода приходится
иметь дело с некоторыми понятиями математического анализа и, прежде всего, из
теории степенных рядов.
Определение 5.
Если степенной ряд
∑
∞
=0n
n
n
xa сходится на множестве
R
X ⊆ к функции
),(x
f
то она называется производящей функцией для последовательности
.}{
0
∞
=nn
a
Проиллюстрируем идею метода производящих функций следующей задачей.
Если необходимо найти все члены некоторой числовой последовательности, то сна-
чала с помощью рекуррентного соотношения для общего члена последовательности
n
a или, исходя непосредственно из комбинаторных соображений, находят произво-
дящую функцию, а затем для нее – ряд Маклорена. Коэффициент этого степенного
ряда при
n
x и будет искомым выражением для общего члена числовой последова-
тельности.
Пример 18. Найти число сочетаний из
m
по
n
с повторениями, т.е. .
n
m
f
Решение. Для
n
m
f из формулы (25) имеем следующее рекуррентное соотношение
.
1
1 n
m
n
m
n
m
fff
−
−
+= (30)
Для того чтобы равенство (30) имело место и при ,1
=
n достаточно считать, что
1
0
=
m
f в дополнение к равенствам (27).
Пусть
−
)(xS
m
производящая функция для последовательности ,}{
0
∞
=n
n
m
f
тогда
∑
∞
=
=
0
)(
n
nn
mm
xfxS . (31)
Умножим обе части равенства (30) на
),...2,1( ∞=nx
n
и сложим почленно все ра-
венства, тогда получим
∑∑ ∑
∞
=
∞
=
∞
=
−
−
+=
11 1
1
1
.
nn n
nn
m
nn
m
nn
m
xfxfxf (32)
Но
∑∑∑
∞
=
∞
=
−−−
∞
=
=⋅=−=
11
111
1
),(,1)(
nn
m
nn
m
nn
m
n
m
nn
m
xxSxfxxfxSxf
∑
∞
=
−−
−=
1
11
1)(
n
m
nn
m
xSxf и, подставляя эти суммы в (32), имеем
,
1
)(
)(
1
x
xS
xS
m
m
−
=
−
откуда следует .
)1(
)(
...
)1(
)(
1
1
2
2
−
−
−
==
−
=
m
m
m
x
xS
x
S
xS
Так как
,1:,...}2,1,0{
1
=∈∀
n
fn
то
