Комбинаторика
1 1 1 1 1 1 1 1 1 1 Рейтинг 0.00 (0 Голоса)

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

Пусть имеется некоторая последовательность чисел . Рассмотрим степенной ряд.

.

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

И уже знакомое нам

,

Можно утверждать, что для последовательностей: 1,1,...,1,... ; 1,2,3,...,n,..., и Производящими функциями являются функции 1/(1-x), 1/(1-x)2 и (1+x)k соответственно.

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

И многие другие соотношения, полезные в комбинаторике.

Рассматривая перестановки в некотором множестве с n элементами, была получена формула (2.2): , для которой использовались соотношения :

.

Соотношение, в котором текущее значение выражения вычисляется на основе предыдущих, называется Рекуррентным или Рекурсивным. Примером рекуррентного соотношения может служить формула генерирования чисел Фибоначчи

(2.18)

Где текущее значение вычислено на основе значения двух предыдущих. Числа Фибоначчи тесно связанны с комбинаторными коэффициентами. Так, число равно числу всех возможных различных N – последовательностей, состоящих из 0 и 1, в которых содержится не более K – единиц, причём ни одна пара единиц не располагается рядом. Из последнего требования следует, что . Таким образом, K Может принимать значения от 0 до , где символ означает целую часть a.

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


ности изобразить, как на рис. 2.3., где в блоке b1 и bk+1 могут быть нули, а в блоках bj должно быть не менее одного нуля в каждом, причем всего нулей должно быть (n - k).

Рис. 2.3. Схема вычисления чисел Фибоначчи

Очевидно, что, если в последовательности K Единиц, то положение нулей уже фиксировано необходимостью отделить единицы друг от друга. Оставшиеся нулей необходимо распределить по «корзинам» , . Чтобы найти число возможных комбинаций, воспользуемся результатами решения задачи 7 данного раздела. Получим:

Таким образом, для F(n) можем записать:

Или в несколько ином виде:

(2.19)

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

(2.20)

Вместе с тем можно записать:

(2.21)

Сравнивая (2.20) и (2.21), получим рекурентное соотношение:

(2.22)

Где .

Добавить комментарий


Защитный код
Обновить