новая папка 1 / 298011

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ "ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ"

ПРОИЗВОДЯЩИЕ ФУНКЦИИ

Учебное пособие для вузов

Составители: Л.Ю. Кабанцова, Т.К. Кацаран

Воронеж Издательский дом ВГУ 2014

В математике можно выделить два направления: одно изучает непрерывные объекты, другое – дискретные. Часто к изучению одного и того же явления можно подойти с разных точек зрения. Производящие функции, изучению которых посвящено данное учебное пособие, являются примером плодотворной связи между дискретными и непрерывными объектами. Метод производящих функций особенно продуктивен при решении рекуррентных соотношений и комбинаторных задач.

§1. Определение и примеры производящих функций

Идея производящих функций достаточно проста. Числовой последовательности (a0, a1, . . . , an, . . .) (дискретному объекту) поставим в со-

для исследования которого можно применить мощный аппарат математического анализа, в частности, ряды Маклорена, см. [1]. Степенные ряды вида (1) можно складывать, вычитать, умножать, дифференцировать.

Определение. Функция G(x) называется производящей функцией последовательности (a0, a1, a2, . . .) , если для всех x из некоторого

Говорят, что функция G(x) "производит" или "генерирует" последовательность (a0, a1, . . . , an, . . .) , поскольку в разложении функции G(x) в ряд по степеням x , коэффициенты при xn равны an . Обознача-

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

1. Самым известным примером производящей функции является би-

без повторений из n элементов по k , т.е. число подмножеств мощности k множества мощности n , n ≥ k ).

3

2. Другой пример производящей функции дает нам сумма членов бесконечно убывающей геометрической прогрессии

(1 − x)−1 = 1 + x + x2 + . . . .

Здесь функция (1 − x)−1 является производящей для последовательности (1, 1, . . . , 1, . . .) .

3. Для числовой последовательности (1, −2, 3, −4, . . .) производящей функцией будет функция G(x) = (1+x)−2 . В этом легко убедиться, проверив равенство

(1 + x)2(1 − 2x + 3x2 − 4x3 + . . .) = 1, x ≠ −1.

4. Найдем производящую функцию Ga;r(x) последовательности

(a, ar, ar2, ar3, . . .)

Ga;r(x) = a + arx + ar2x2 + ar3x3 + . . . = a(1 + rx + (rx)2 + (rx)3 + . . .).

Из последнего равенства получаем

В приведенных здесь примерах производящие функции являются элементарными. Естественно предположить, что они могут быть представлены более сложными выражениями, которые зависят от свойств последовательности (a0, a1, a2, . . .) . С этой точки зрения полезной является следующая теорема, приведенная в статье [2].

Теорема. Пусть последовательность {an} задается рекуррентным соотношением порядка k с постоянными c1, c2, . . . , ck , т.е.

степень многочлена P не превосходит k − 1 , а степень многочлена Q равна k . Многочлен Q имеет вид

Q(x) = 1 − c1x − c2x2 − . . . − ckxk.

4

С использованными здесь определением рекуррентного соотношения и методами его решения можно познакомиться в работе [3].

Постановка задачи. Имеется некоторая информация о последовательности (a0, a1, a2, . . .) , используя которую нужно найти производящую функцию G(x) . Далее, пользуясь методами математического анализа, найти зависимость коэффициентов an от n , используя найденную на первом этапе производящую функцию.

При этом можно использовать различные методы преобразования степенных рядов вида (1), которые следует рассматривать как формальные, т.е. нет необходимости думать, что x – число и пытаться строгость рассуждений привязать к доказательству сходимости степенных рядов.

Следует учитывать, что справедлива теорема единственности: если при некотором c > 0 функция f(x) представима в виде степенного ряда a0 + a1x + a2x2 + . . . на интервале (−c, c) , то коэффициенты ai , i = 0, 1, . . . определяются однозначно.

§2. Преобразование производящей функции

1)Сложение производящих функций.

Рассмотрим две производящие функции

∑∞

n=0

∑∞

H(x) = bnxn = b0 + b1x + b2x2 + . . . .

n=0

Имеем

[xn](G(x) + H(x)) = an + bn.

2) Умножение на константу.

Результат умножения функции или переменной на константу выражен равенствами:

3) Дифференцирование и интегрирование производящих функций. Пусть G(x) = a0 + a1x + a2x2 + . . . – производящая функция. Дадим формальные определения производной и интеграла производящих

функций. Производной этой функции называется функция

G′(x) = a1 + 2a2x + 3a3x2 + . . . + nanxn−1 + . . . ,

5

интегралом G(x) – функция

Операция дифференцирования обратна операции интегрирования:

(∫ )′

G(x)dx = G(x).

Операция же интегрирования производной приводит к функции с нулевым свободным членом, и поэтому результат, вообще говоря, отличается от исходной функции.

Замечание. Нетрудно видеть, что для функций, представимых степенными рядами, формула для производной соответствует обычной. Формула для интеграла соответствует значению интеграла с переменным верхним пределом

∫∫x

G(x)dx = G(s)ds.

0

4) Сдвиг.

Умножим левую и правую части равенства (7) на xm :

∑∞

xmG(x) = xm anxn = a0xm + a1xm+1 + a2xm+2 + . . . .

n=0

Полученная функция генерирует новую последовательность

(0, . . . , 0, a0, a1, . . .),

которая является сдвигом исходной последовательности на m элементов

5) Полиномиальный множитель и делитель.

Полиномиальный множитель " n "возникает при умножении производной производящей функции на x . Появление делителя в генерируемой производящей функцией последовательности возникает в результате

6

Таким образом,

6) Произведение производящих функций.

Перемножим производящие функции G(x) и H(x) (см. (7)):

F (x) = G(x) · H(x) = a0b0 + (a0b1 + a1b0)x + (a0b2 + a1b1 + a2b0)x2 + . . . =

∑∞ (∑n )

Сумму, взятую в скобки, принято называть сверткой производящих функций G(x) и H(x) (обозначим ее через cn ):

Мы получаем, что функция G(x)/(1−x) генерирует последовательность

7

G(x) = 1 , а в правой части соответствующую этой функции генерирующую последовательность (1, 0, 0, . . .) , получим:

Используя найденную функцию F1(x) в качестве G(x) в равенстве (14), находим

В приведенных выражениях символ обозначает взаимно-однозначное соответствие между производящей функцией, стоящей слева, и "генерируемой" ею последовательностью, стоящей справа.

Для того чтобы найти для производящей функции 1/(1 − x)m генерирующую ее последовательность, нужно использовать равенство (14) и найденный на (m − 1) -ом шаге результат.

Легко доказать, что общий член генерирующей последовательности

Для доказательства этого равенства можно использовать метод математической индукции или формулу разложения в ряд Маклорена функции

1/(1 − x)m .

§3. Рациональные производящие функции

Найденные в предыдущем параграфе производящие функции относятся к классу элементарных рациональных функций. Рациональные производящие функции образуют большой класс производящих функций. Производящие функции, встречающиеся на практике, очень часто принадлежат к этому классу. Кроме того, теория рациональных производящих функций совпадает, по существу, с теорией обыкновенных дифференциальных уравнений с постоянными коэффициентами.

Легко убедиться, что производящая функция последовательности Фибоначчи

1, 1, 2, 3, 5, 8, . . . ,

8

в которой каждый последующий член, начиная с третьего, является суммой двух предыдущих, является рациональной. Рекуррентное соотношение

впервые было опубликовано в 1202 г. в книге Леонардо Пизанского (Фибоначчи) "Liber abaci"при решении задачи о размножении кроликов. Нужно было ответить на вопрос "Сколько пар кроликов в один год рождаются от одной пары?"

Чтобы вывести формулу производящей функции

умножим обе части равенства (20) на (x + x2) . Получим

(x + x2)φ(x) = x + x2 + 2x3 + 3x4 + . . . + x2 + x3 + 2x4 + 3x5 + . . . =

= x + 2x2 + 3x3 + 5x4 + . . .

или

(x + x2)φ(x) = φ(x) − 1,

откуда следует представление

1

φ(x) = 1 − x − x2 .

Полученную формулу можно понимать как композицию двух производящих функций, а именно (1 − x)−1 и x + x2 :

φ(x) = 1 + (x + x2) + (x + x2)2 + (x + x2)3 + . . . .

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

Теорема. Если производящая функция G(x) = a0 + a1x+ a2x2 + . . .

рациональна, G(x) = P (x) , где многочлены P (x) и Q(x) взаимно

Q(x)

просты, то, начиная с некоторого номера n , последовательность a0, a1, a2, . . . задается линейным рекуррентным соотношением

an+k = c1an+k−1 + c2an+k−2 + . . . + ckan,

где k - степень многочлена Q , а c1, c2, . . . , ck некоторые постоянные.

9

§4. Производящие функции и решение рекуррентных соотношений

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

Пусть последовательность (a0, a1, a2, . . .) удовлетворяет некоторому рекуррентному соотношению.

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

1.Записать рекуррентное соотношение и начальные данные для него

вследующем виде (если порядок соотношения равен k ):

a0 = . . . , a1 = . . . ,

· · · · · · · · ·

ak−1 = . . . ,

an = f(an−k+1, an−k, . . .), n ≥ k.

2. Умножить каждую строку на x в соответствующей номеру строки

G(x) .

4. Выразить G(x) в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням x .

Пример 1. Решить рекуррентное соотношение a0 = 0 , a1 = 1 , an = 5an−1 − 6an−2 (n ≥ 2) с помощью производящей функции.

Шаг 1. Запишем заданное рекуррентное соотношение в виде:

a0 = 0, a1 = 1,

an = 5an−1 − 6an−2, n ≥ 2.

Шаг 2. Умножим верхнюю строку записи на x0 , следующую на x1 и последнюю на xn :

1 · a0 = 0 · 1,

x · a1 = 1 · x,

xn · an = (5an−1 − 6an−2)xn, n ≥ 2.

1Нужно образовать суммы с пределами суммирования от 0 до ∞

10