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

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

Пусть задана последовательность комбинаторных чисел { } и последо-вательность функций { } ( i = 0, 1, … }.

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

F(x) = (4.9)

Пример. Пусть , ( i = 0, 1, …, n ), .

В этом случае в качестве производящей функции будет бином Ньютона, т.е.

F(x) = ( 1 + x ) = (4.10)

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

(4.11)

Для этого запишем тождество ( 1 + x ) = ( 1 + x ) ( 1 + x ) . Оно будет эквивалентно следующему тождеству

.

Приравнивая коэффициенты при x в обеих частях этого равенства, получим

.

Иногда удается использовать свойства последовательности { } для нахождения уравнения в которое входит производящая функция F(x). Если удается решить это уравнение, то можно получить выражения для { }.

В качестве примера рассмотрим такой случай с числами Фибоначчи, которые определяются следующими рекуррентными соотношениями

= = 1,

= + , n > 1.

Запишем производящую функцию для этой последовательности при .

Из (4.1) получим

F(x) = (4.12)

Это выражение запишем в следующем виде

F(x) = + x + = + x + + =

= + x + + .

Легко видеть, что первая сумма в этом выражении равна x ( F(x) - ), а вторая x F(x). Тогда F(x) можно записать так

F(x) = + x + x F(x) + x ( F(x) – ).

Учитывая, что = = 1, получим

F(x) = 1 + x + x F(x) + x (F(x) – 1 )

Откуда получим

F(x) = .

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

1 – x - x = ( 1 - x)( 1 – bx) , где = , b = .

Тогда

F(x) = , где А = , B = .

Учитывая, что при малых x справедливо

,

получим F(x) = (4.13)

Сравнивая (4.12) и (4.13) получим следующие выражения для членов последовательности в виде

= .

Можно проверить непосредственно, что это выражение удовлетворяет рекуррентным соотношениям для чисел Фибоначчи.

СПИСОК ЛИТЕРАТУРЫ

1. Яблонский С.В. Введение в дискретную математику. М.:Высш. Шк.,2001.

2. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. М.,:

Наука, 1977.

3. Нефедов В.Н.,Осипова В.А. Курс дискретной математики. М.: Изд-во МАИ, 1992.

4. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. М.:

Вузовская книга, 2001.

5. Карпов Ю.Г. Теория автоматов. СПб.: Питер, 2002.

6. Кобринский Н.Е., Трахтенброт Б.А. Введение в теорию конечных автоматов.

Физматгиз, М., 1962.

7. Кузнецов О.П., Адельсон–Вельский Г.М. Дискретная математика для инженера. М.:

Энергия, 1988.

8. Романовский И.В. Дискретный анализ. СПб.: Невский диалект, 2000.

9. Лексаченко В.А. Логика. Множества. Вероятность. М.: Вузовская книга, 2001.

10. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и

теории алгоритмов. М.: Физматлит, 2001.

11. Горбатов В.А. Основы дискретной математики. М.: Высш. Шк., 1986.

12. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: Учебник.

М.: ИНФРА-М., 2002.

13. Оре О. Теория графов. М.: Наука, 1980.

14. Гиндикин С.Г. Алгебра логики в задачах. М.: Наука, 1972.

97