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

 

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

Здесь необходимо знать: понятие ряда, сумма ряда, степенной ряд, сходимость степенных рядов, свойства сходящихся рядов, операции над ними. Эти понятия изложены в любом учебнике по математическому анализу, и мы их опускаем.

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

Примеры: 1) Для степенного ряда , члены которого можно рассматривать как геометрическую прогрессию, знаменатель . Значит, степенной ряд при условии сходится к своей сумме . Таким образом, получаем:

, если .

Значит, функция является производящей для последовательности чисел (коэффициенты степенного ряда).

2) Аналогично можно получить:

.

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

3) Из формулы бинома Ньютона следует:

,

т.е. функция является производящей для чисел вида , где .

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

;

;

(здесь обе суммы конечны и обрываются, когда значения и станут больше ).

Кроме того:

,

,

.

В последнем равенстве, если , то считают, что . Поэтому меняется от до наименьшего из чисел , .

Последнее равенство можно доказать следующим образом:

,

.

Отсюда следует: .

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

В частном случае, когда , получаем равенство:

, .

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

1) Рассмотрим разбиение числа на слагаемые, каждое из которых равно одному из чисел . При этом слагаемые не повторяются и их порядок не играет роли.

Для решения задачи рассмотрим выражение . Раскрывая скобки, получим слагаемые вида , где – некоторые из чисел . Поэтому встретится в сумме столько раз, сколькими способами можно разбить на слагаемые требуемым образом.

Например, если надо узнать, сколькими способами можно заплатить 78 копеек, беря не более одной монеты каждого достоинства, то надо составить выражение:

,

раскрыть скобки и найти коэффициент при слагаемом .

2) Если требуется разложить число на слагаемые , каждое из которых может встречаться в разложении один или несколько раз, тогда количество слагаемых в скобках увеличивается.

Например: 1) Сколькими способами можно заплатить 29 коп., используя монеты по 2 и 5 коп?

Т.е. надо найти число способов разбить число 29 на слагаемые, равные 2 и 5, причем порядок слагаемых роли не играет, и каждое слагаемое может повторяться несколько раз. Для этого составим выражение:

.

Ясно, что при раскрытии скобок выражение войдет в разложение с коэффициентом, равным числу решений уравнения . В частности, коэффициент при дает ответ на вопрос задачи.

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

.

Разделив «уголком» числитель на знаменатель, находим коэффициент при выражении .

2) Поступающий в ВУЗ должен сдать 4 экзамена, причем для поступления достаточно набрать 17 балов. Сколькими способами абитуриент может сдать экзамены, чтобы поступить в ВУЗ?

Требуется узнать, сколькими способами можно представить число 17 в виде суммы 4-х слагаемых, принимающих значения 3, 4, 5, причем здесь порядок слагаемых имеет значение.

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

В выражении можно раскрыть скобки по полиномиальной теореме, а можно следующим образом:

.

Поэтому .

.

Перемножая почленно эти выражения, найдем, что коэффициент при равен 16. Значит, разложение можно сделать 16 способами.

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

Пусть - производящая функция для последовательности чисел . Это означает, что является суммой степенного ряда: .

Пусть – многочлены, причем и , значит, дробь – правильная (в противном случае можно выделить целую часть). Раскладывая дробь в ряд, получим:

.

Раскрывая скобки справа и приравнивая коэффициенты при одинаковых степенях , получаем:

При считаем, что . А дальше все соотношения имеют вид: , где , т.к. не имеет членов степени , , …

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

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

Полученную алгебраическую дробь можно разлагать на элементарные дроби и производить алгебраические преобразования.