МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
"ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ"
ПРОИЗВОДЯЩИЕ ФУНКЦИИ
Учебное пособие для вузов
Составители:
Л.Ю. Кабанцова,
Т.К. Кацаран
Воронеж
Издательский дом ВГУ
2014
Стр.1
В математике можно выделить два направления: одно изучает
непрерывные объекты, другое – дискретные. Часто к изучению одного и
того же явления можно подойти с разных точек зрения. Производящие
функции, изучению которых посвящено данное учебное пособие, являются
примером плодотворной связи между дискретными и непрерывными
объектами. Метод производящих функций особенно продуктивен при
решении рекуррентных соотношений и комбинаторных задач.
§ 1. Определение и примеры производящих функций
Идея производящих функций достаточно проста. Числовой последовательности
(a0, a1, . . . , an, . . .) (дискретному объекту) поставим в соответствие
степенной ряд (непрерывный объект)
a0 +a1x+. . .+anxn +. . . , x ∈ R,
(1)
для исследования которого можно применить мощный аппарат математического
анализа, в частности, ряды Маклорена, см. [1]. Степенные ряды
вида (1) можно складывать, вычитать, умножать, дифференцировать.
Определение.
Функция G(x) называется производящей функцией
последовательности (a0, a1, a2, . . .) , если для всех x из некоторого
открытого множества выполняется равенство
G(x) = a0 +a1x+a2x2 +. . . .
(2)
Говорят, что функция G(x) "производит" или "генерирует" последовательность
(a0, a1, . . . , an, . . .) , поскольку в разложении функции
G(x) в ряд по степеням x, коэффициенты при xn равны an . Обозначается
этот факт с помощью записи
[xn]G(x) = an.
(3)
Приведем несколько примеров хорошо известных производящих
функций.
1. Самым известным примером производящей функции является бином
Ньютона
(1+x)n = C0
где Ck
n +C1
nx+. . .+Ck
nxk +. . .+Cn
nxn,
(4)
без повторений из n элементов по k , т.е. число подмножеств мощности
k множества мощности n, n ≥ k ).
3
n = n!
k!(n−k)! – биномиальные коэффициенты (число сочетаний
Стр.3
интегралом G(x) – функция
∫
G(x)dx = a0x+a1
x2
2 +a2
G(x)dx
x3
3 +. . .+an
)′
= G(x).
n+1 +. . . .
xn+1
Операция дифференцирования обратна операции интегрирования:
(∫
Операция же интегрирования производной приводит к функции с нулевым
свободным членом, и поэтому результат, вообще говоря, отличается
от исходной функции.
Замечание. Нетрудно видеть, что для функций, представимых
степенными рядами, формула для производной соответствует обычной.
Формула для интеграла соответствует значению интеграла с переменным
верхним пределом
∫
G(x)dx =
∫x
0
G(s)ds.
4) Сдвиг.
Умножим левую и правую части равенства (7) на xm:
xmG(x) = xm
∑
n=0
∞
anxn = a0xm +a1xm+1 +a2xm+2 +. . . .
Полученная функция генерирует новую последовательность
(0, . . . , 0, a0, a1, . . .),
которая является сдвигом исходной последовательности на m элементов
вправо, то есть
[xn](xmG(x)) =
{ 0, n < m,
an−m, n ≥ m.
(9)
5) Полиномиальный множитель и делитель.
Полиномиальный множитель "n"возникает при умножении производной
производящей функции на x. Появление делителя в генерируемой
производящей функцией последовательности возникает в результате
интегрирования. Проведем преобразования:
xG′(x) = x
( ∞
∑
n=0
6
anxn
)′
= x
( ∞
∑
n=0
nanxn−1
)
=
∑
n=0
∞
nanxn.
Стр.6
Таким образом,
[xn](xG′(x)) = nan.
Аналогично,
∫x
0
G(t)−a0
t
[xn]
[xn]
dt =
∫x
0
∫x
0
( ∞
∑
n=1
G(t)−a0
t
∫x
0
G(t) dt
dt
= an
= an−1
antn−1
)
dt =
∑
n=1
∞
n , n ≥ 1.
n , n ≥ 1.
6) Произведение производящих функций.
Перемножим производящие функции G(x) и H(x) (см. (7)):
F(x) = G(x) ·H(x) = a0b0+(a0b1+a1b0)x+(a0b2+a1b1+a2b0)x2+. . . =
=
∑
n=0
∞ ( n
∑
k=0
)
akbn−k
xn.
(13)
Сумму, взятую в скобки, принято называть сверткой производящих
функций G(x) и H(x) (обозначим ее через cn ):
n
cn =
∑
k=0
akbn−k.
Рассмотрим частный случай. Пусть bn = 1, тогда (так как
производящая функция последовательности (1, 1, . . .) )
∑
n=0
∞ ( n
∑
k=0
)
1−x –
1
F(x) = G(x) 1
1−x = a0 +(a0 +a1)x+(a0 +a1 +a2)x2 +. . . =
=
ak
xn.
an
n xn.
(11)
(12)
(10)
(14)
Мы получаем, что функция G(x)/(1−x) генерирует последовательность
частичных сумм исходной последовательности an .
Теперь мы можем получить разложение в ряд дробей вида
1/(1 − x)m,m = 1, 2, 3, . . . . Полагая в левой части равенства (14)
7
Стр.7
G(x) = 1, а в правой части соответствующую этой функции генерирующую
последовательность (1, 0, 0, . . .) , получим:
F1(x) = 1
1−x ⇔ (1, 1, 1, . . .) = (1)n≥0.
F2(x) = 1
(1−x)2 ⇔ (1, 2, 3, 4, . . .) = (n+1)n≥0.
Продолжая этот процесс дальше, находим:
F3(x) = 1
(1−x)3 ⇔ (1, 3, 6, 10, . . .) =
((n+1)(n+2)
2
)
n≥0
В приведенных выражениях символ ⇔ обозначает взаимно-однозначное
соответствие между производящей функцией, стоящей слева, и "генеририрующую
ее последовательность, нужно использовать равенство (14) и
для функции 1/(1−x)m равен
Fm(x) = 1
(1−x)m ⇔
(n+1) . . . (n+m−1)
(m−1)!
= Cn
n+m−1.
(18)
Для доказательства этого равенства можно использовать метод математической
индукции или формулу разложения в ряд Маклорена функции
1/(1−x)m.
§ 3. Рациональные производящие функции
Найденные в предыдущем параграфе производящие функции относятся
к классу элементарных рациональных функций. Рациональные
производящие функции образуют большой класс производящих функций.
Производящие функции, встречающиеся на практике, очень часто
принадлежат к этому классу. Кроме того, теория рациональных производящих
функций совпадает, по существу, с теорией обыкновенных
дифференциальных уравнений с постоянными коэффициентами.
Легко убедиться, что производящая функция последовательности
Фибоначчи
1, 1, 2, 3, 5, 8, . . . ,
8
руемой" ею последовательностью, стоящей справа.
Для того чтобы найти для производящей функции 1/(1−x)m гененайденный
на (m−1)-ом шаге результат.
Легко доказать, что общий член генерирующей последовательности
. (17)
(15)
Используя найденную функцию F1(x) в качестве G(x) в равенстве (14),
находим
(16)
Стр.8