Замечательные комбинаторные числа

S(n, k) = S(n – 1, k – 1) + k *S(n – 1, k), n > 0

Таблица 1. Треугольник Стирлинга для числа подмножеств

n	S(0,n)	S(1, n)	S(2, n)	S(3, n)	S(4, n)	S(5, n)	S(6, n)	S(7, n)	S(8,n)	S(9,n)
0	1
1	0	1
2	0	1	1
3	0	1	3	1
4	0	1	7	6	1
5	0	1	15	25	10	1
6	0	1	31	90	65	15	1
7	0	1	63	301	350	140	21	1
8	0	1	127	966	1701	1050	266	28	1
9	0	1	255	3025	7770	6951	2646	462	36	1

2. Числа Стирлинга  первого рода.

Символом s(n, k) обозначается количество способов представления n объектов в виде k циклов. s(n, k) читается так: k циклов из n.

Например, циклы  из 4 элементов [a, b, c, d],  [b, c, d, a], [c, d, a, b] и [d, a, b, c]  являются одинаковыми. Цикл можно прокручивать, так как его конец соединен с началом.

Существует 11 различных способов составить два цикла из четырех элементов:

[1, 2, 3][4], [1, 2, 4][3], [1, 3, 4][2], [2, 3, 4][1],

[1, 3, 2][4], [1, 4, 2][3], [1, 4, 3][2], [2, 4, 3][1],

[1, 2][3, 4], [1, 3][2, 4], [1, 4][2, 3].

Поэтому s(4, 2) = 11.

Единичный цикл (цикл, состоящий из одного элемента) – это то же самое, что и единичное  множество. 2-цикл подобен 2-множеству, поскольку [A, B] = [B, A] как и      {A, B} = {B, A}. Однако уже существует два различных 3-цикла: [A, B, C] и [A, C, B]. Из любого n-элементного множества могут быть составлены = (n – 1)! циклов, если n > 0 (всего имеется n! перестановок, а каждый цикл соответствует сразу n из них, так как отсчет цикла может быть начат с любого из его элементов). Поэтому

s(n, 1) = (n – 1)!

Если все  циклы являются единичными или двойными, то s(n, k) =  S(n, k). Например,

s(n, n) = S(n, n) = 1, 

s(n, n – 1 )= S(n, n – 1)=

Выведем рекуррентную формулу для вычисления чисел  Стирлинга первого рода. Каждое представление n объектов в виде k циклов либо помещает последний объект в отдельный цикл s(n – 1, k – 1) способами, либо вставляет этот объект в одно из s(n – 1, k) циклических представлений первых n – 1 объектов. В последнем случае существует n – 1 различных способов подобной вставки. Например, при вставке элемента d в цикл [a, b, c] можно получить только 3 разных цикла: [a, b, c, d], [a, b, d, c], [a, d, b, c]. Таким образом, рекуррентность имеет вид:

s(n, k)= s(n – 1, k – 1) + (n – 1) *s(n – 1, k), n > 0

Таблица 2. Треугольник Стирлинга для числа циклов

n	s(0, n)	s(1, n)	s(2, n)	s(3, n)	s(4, n)	s(5, n)	s(6, n)	s(7, n)	s(8,n)	s(9, n)
0	1
1	0	1
2	0	1	1
3	0	2	3	1
4	0	6	11	6	1
5	0	24	50	35	10	1
6	0	120	274	225	85	15	1
7	0	720	1764	1624	735	175	21	1
8	0	5040	13068	13132	6769	1960	322	28	1
9	0	40320	109584	118124	67284	22449	4536	546	36	1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. ЧИСЛА БЕЛЛА

Белл Эрик Темпл (1883 – 1960) – американский математик шотландского происхождения.

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

Число Белла B_n равно количеству разбиений множества из n элементов на произвольное количество непустых подмножеств. Очевидно, что B₀ = 1, так как существует только одно разбиение пустого множества. Например, B₃ = 5, так как существует 5 возможных разбиений множества {a, b, c} из трех элементов:

{{a}, {b}, {c}}, {{a, b}, {c}}, {{a, c}, {b}}, {{a}, {b, c}},  {{a, b, c}}

Заметим, что n элементов можно разбить на i множеств (1 £ i £ n). При этом количество разбиений n - элементного множества на k подмножеств равно числу Стирлинга 2 рода S(n, k). Откуда получаем формулу:

B_n =

Таблица 3. Таблица чисел Белла

n	0	1	2	3	4	5	6	7	8	9	10
Bn	1	1	2	5	15	52	203	877	4140	21147	115975

 

Рассмотрим  следующие конструкции, в которых  точки обозначают одноэлементные множества, а сегменты объединяют элементы, принадлежащие  одному множеству. Из n элементов можно построить B_n разных таких конструкций (рис. 11).

рис.11

Теорема. Числа Белла удовлетворяют следующему рекуррентному соотношению:

 

Доказательство. Рассмотрим разбиение n +1 элемента в зависимости от величины блока, в котором находится (n + 1) - ый элемнент. Пусть размер этого блока равен j (1 £ j £ n + 1). Тогда существует способов выбрать в него кроме (n + 1) - ого еще j – 1 элемент. Остальные n + 1 – j элементов можно разбить B_{n + 1 – j} способами.Таким образом:

 

Например, B₄ = B₀ + B₁ + B₂ + B₃ = 1 * 1 + 3 * 1 + 3 * 2 + 1* 5 = 15.

2. Свойства

• Числа Белла удовлетворяют следующему свойству:

 

Для значений n = 0, 1, 2, … получим следующие значения детерминанта:

1, 1, 2, 12, 288, 34560, 24883200, 125411328000, 5056584744960000,

1834933472251084800000, 6658606584104736522240000000, …

• При разложении функции   в ряд Маклорена коэффициенты ряда образуют числа Белла:

 

• Числа B_n могут быть построены при помощи треугольника Белла. Первая строка содержит 1. Каждая следующая строка начинается числом, стоящим в конце предыдущей строки. Каждое следующее число в строке равно сумме чиcел, стоящих слева и сверху от него. Числа Белла образуют последние числа в строках.

 

Таблица 4. Треугольник Белла

									1
						1				2
					2		3				5
				5		7				10		15
			15		20			27			37		52
		52		67		87				114		151		203
	203		255		322		409				523		674		877
877		1080		1335		1657				2066		2589		3263		4140

4. ЧИСЛА ФИБОНАЧЧИ

Леонардо Пизанский, больше известный под прозвищем Фибоначчи  (около 1170 – около 1250) – первый крупный математик средневековой Европы.

Таблица 5. Числа Фибоначчи

n	0	1	2	3	4	5	6	7	8	9	10
	0	1	1	2	3	5	8	13	21	34	55

Числа Фибоначчи определяются рекуррентным соотношением:

 = 0,

 = 0,

 = +   для n>1

Бесхитростность этого правила, в котором каждое число зависит от двух предыдущих, служит объяснением того, почему числа  Фибоначчи встречаются в самых  разнообразных ситуациях.

1. Задача о  кроликах.

Формулировка и решение  этой задачи считается основным вкладом  Фибоначчи в развитие комбинаторики. Именно с помощью этой задачи Фибоначчи  предвосхитил метод рекуррентных соотношений, который считается одним из мощных методов решения комбинаторных задач.

Существо своей "задачи о размножении кроликов" Фибоначчи  сформулировал предельно просто: «Пусть в огороженном месте имеется пара кроликов (самка и самец) в первый день января. Эта пара кроликов производит новую пару кроликов в первый день февраля и затем в первый день каждого следующего месяца. Каждая новорожденная пара кроликов становится зрелой уже через месяц и затем через месяц дает жизнь новой паре кроликов. Возникает вопрос: сколько пар кроликов будет в огороженном месте через год, то есть через 12 месяцев с начала размножения?»

рис.11

Для решения этой задачи, которая наглядно демонстрируется  с помощью рисунка, обозначим  через A пару зрелых кроликов, а через B - пару новорожденных кроликов. Тогда процесс "размножения" может быть описан с помощью двух "переходов", которые описывают ежемесячные превращения кроликов в процессе размножения:

А→АВ                  (1)

В→А                     (2) 

Заметим, что  переход (1) моделирует ежемесячное  превращение каждой зрелой пары кроликов А в две пары, а именно в ту же самую пару зрелых кроликов А и новорожденную пару кроликов В. Переход (2) моделирует процесс "созревания" кроликов, когда новорожденная пара кроликов В через месяц превращается в зрелую пару А. Тогда, если мы начнем в первом месяце со зрелой пары А, тогда процесс размножения кроликов может быть представлен с помощью таблицы.

Таблица 6. Процесс размножения кроликов

Дата	Пары кроликов	А	В	А + В
1-го января	А	1	0	1
1-го февраля	АВ	1	1	2
1-го марта	АВА	2	1	3
1-го апреля	АВААВ	3	2	5
1-го мая	АВААВАВА	5	3	8
1-го июня	АВААВАВААВААВ	8	5	13