Лекции. Теория графов и комбинаторика (стр. 12 )

Утверждение 1.

4Пусть n-множество . Все его разбиения можно разделить на 2 группы:

1.  Те, которые содержат блок . Их число равно числу разбиений (n – 1)-подмножества на (k – 1) блоков, т. е. .

2.  Те, которые не содержат блок . Они соответствуют разбиениям подмножества на k блоков, и в любой из этих k блоков поместим . Таких разбиений ровно .

По правилу суммы .3

Следствие.

Из начальных условий

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

	0	1	2	3	4	...	k
0	1							1
1	0	1						1
2	0	1	1					2
3	0	1	3	1				5
4	0	1	7	6	1			15
n

Числа Стирлинга II рода применяются во многих задачах, в частности:

Пример («Задача о пирогах и тарелках», один из вариантов).

Сколькими способами можно n различных пирогов разложить по k различным тарелкам так, чтобы не было пустых тарелок?

Ответ:

Пример (задача эквивалентна предыдущей).

Найти число сюръекций n-множества А на k-множество B.

Ответ:

Пример.

Числа Белла – число всех разбиений n-множества, оно же равно числу отношений эквивалентности на n-множестве.

Утверждение 2.

4Пусть (n+1)-множество . Все его разбиения можно получить так: взять разбиение k-подмножества множества и в каждый его блок (любой из ) поместить элемент . Если k изменять от 0 до n, то мы получим все разбиения U.3

Можем построить таблицу чисел Белла:

n	0	1	2	3	4	5	...
	1	1	2	5	15	52	...

Пример («Задача Фибоначчи о кроликах», монах Леонардо Пизанский, XI в).

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

– количество пар кроликов спустя n месяцев.

(через месяц исходные кролики ещё не размножаются).

– рекуррентное уравнение для чисел Фибоначчи и начальные условия.

Можем построить таблицу чисел Фибоначчи:

n	0	1	2	3	4	5	...
	1	1	2	3	5	8	...

4Выведем замкнутую формулу для чисел Фибоначчи, т. е. выразим только через n.

Пусть – производящая функция для последовательности чисел Фибоначчи.

Тогда сдвинув последовательность влево на 1, получим , а при сдвиге последовательности влево на 2 получим .

Т. к. образом, переходя от рекуррентного уравнения к уравнению для ПФ, получим .

Корни многочлена обозначим как , тогда

равно коэффициенту при : . Не смотря на эти иррациональности, все целые.3

Определение 1.

Уравнение называется рекуррентным уравнением порядка k для последовательности В данном случае члены последовательности могут быть любыми числами, коэффициенты тоже, т. е. .

Если , то уравнение называется однородным.

Утверждение 3.

Если , то неоднородное уравнение сводится к однородному заменой для некоторой .

4 подставляем в уравнение:

. Уравнение станет однородным, если 3

Метод решения однородных линейных уравнений порядка k аналогичен методу решения однородных линейных дифференциальных уравнений порядка k.

Определение 2.

Алгебраическое уравнение относительное

степени k называется характеристическим уравнением для .