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

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

.

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

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

,

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

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

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

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

.

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

(2.18)

где текущее значение вычислено на базе значения 2-ух прошлых. Числа Фибоначчи тесновато связанны с комбинаторными коэффициентами. Так, число равно числу всех вероятных разных n – последовательностей, состоящих из 0 и 1, в каких содержится менее k – единиц, причём ни одна пара Производящие функции. Рекуррентные соотношения единиц не размещается рядом. Из последнего требования следует, что . Таким макаром, k может принимать значения от 0 до , где знак значит целую часть a.

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


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

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

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

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

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

(2.19)

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

(2.20)

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

(2.21)

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

(2.22)

где .

Задачки и упражнения

1. Сколько существует перестановок из n частей, в каких меж 2-мя данными элементами стоит r частей?

2. Сколькими методами можно расположить n гостей за круглым столом?

3. Сколько разных слов можно составить, переставляя буковкы слова «комбинаторика»?

4. Сколько Производящие функции. Рекуррентные соотношения можно сделать костей домино, используя числа 0,1,...,r?

5. Сколько целых положительных решений имеет уравнение x1+x2+...+xm=n?

6. Обосновать, что для биномиальных коэффициентов справедливо равенство

7. Способом траекторий либо другим методом обосновать, что

8. Обосновать, что если k<(n-1)/2 и если k>(n-1)/2.

9. Отыскать наибольшее посреди чисел .

10. Обосновать, что сумма всех полиномиальных коэффициентов в разложении (x1+x Производящие функции. Рекуррентные соотношения2+...+xk)n равно kn.

11. Используя биномиальное разложение, обосновать тождества:

а) ;

б) ;

в) .

12. Используя характеристики биномиального разложения, вычислить:

а) ;

б) ;

в) .

13. Найти количество прямоугольных матриц размерности с элементами из {0,1} с попарно разными строчками (m<=2 ).

14. Из колоды, состоящей из 52 карт, избрали 10 карт. Найти, в скольких случаях посреди их окажутся:

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

г) ни 1-го туза; д) ровно один туз; е) хотя бы один туз;

ж) ровно два туза.

15. Отыскать количество целочисленных решений системы:

а) ;

б) .

16. Вывести соотношение (2.19) для чисел Фибоначчи, используя идеи задачки 2.7 этого раздела.


proizvolnost-derevev-poiska.html
projdite-diagnostiku-do-nachala-snizheniya-vesa-periodicheski-proveryajte-sostoyanie-svoego-organizma-v-processe-izbavleniya-ot-lishnih-kilogrammov.html
prokachivanie-predplechij.html