Числа стирлинга второго рода формула

Тема: разбиения на блоки и циклы

Основные вопросы, рассматриваемые на лекции:

1. Разбиения множества на m блоков.

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

3. Разбиения перестановки на m циклов.

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

5. Факториальные многочлены.

Краткое содержание лекционного материала

1. Разбиения множества на m блоков. Говорят, что семейство множеств <M₁,…,M_k> является разбиением множества M на k блоков M₁,…,M_k, если M₁,…,M_k – непустые, попарно не пересекающиеся, подмножества множества M и объединение множеств M₁,…,M_k есть множества M. Число (или S(n,k)) всех разбиений n-множества M на k блоков называется числом Стирлинга второго рода.

Пример 1. Перечислим все разбиения множества <1,2,3,4>на 2 блока:

Мы видим, что .

Примечание. Пусть |A|=m, |B|=n. Тогда число элементов:

· множества всех отображений множества A в B равно числу всех размещений с повторениями по m из n, то есть |B A |=n m ;

· множества всех инъекций множества A в B равно числу всех размещений без повторений по m из n, то есть ;

· множества всех биекций множества A на B равно числу всех размещений без повторений по m из n, то есть n!;

· множества всех сюръекций множества A на B равно произведению числа всех перестановок n-множества B на число всех разбиений n-множества B на m блоков, то есть n!.

2. Число Стирлинга второго рода. Приведем рекуррентные формулы для числа Стирлинга второго рода:

;

, где n>0;

, где n>0, 1£k£n.

Непосредственно число Стирлинга второго рода вычисляется по следующей формуле: .

Число всех разбиений n-множества M называется числом Белла B_n.

Ясно, что .

Пример 2. Перечислим все перестановки множества <1,2,3,4>, разбиваемые на 2 цикла:

Числом Стирлинга первого рода (без знака) (или s(n,k)) называется число разбиений n-множества B на k циклов.

4.Число Стирлинга первого рода. Приведем рекуррентные формулы для числа Стирлинга первого рода

;

, где n>0;

, где n>0, 1£k£n.

Ясно, что .

5. Факториальные многочлены.Любой многочлен от одной переменной можно представить как линейную сумму степеней переменной (базисных многочленов): , , , …

Определим многочлены , , которые также являются базисными: .

Связь между двумя базисными многочленами устанавливается при помощи чисел Стерлинга первого и второго родов:

, .

Вместо «убывающих степеней» можно рассматривать «возрастающие степени»: .

, .

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Только сон приблежает студента к концу лекции. А чужой храп его отдаляет. 8958 — | 7623 — или читать все.

91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)
очень нужно

Числа Стирлинга второго рода (англ. stirling numbers of the second kind) — количество способов разбиения множества из [math]n[/math] элементов на [math]k[/math] непустых подмножеств. Числа Стирлинга II рода обозначаются как [math]S(n,k)[/math] или [math]lbrace
brace[/math] .

Содержание

Пример [ править ]

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

Следовательно, [math]lbrace<4atop 2>
brace[/math] [math] = 7[/math] .

Вычисление [ править ]

Рекуррентное соотношение [ править ]

Если задано множество из [math]n[/math] элементов, которое необходимо разбить на [math]k[/math] непустых частей, то последний элемент исходного множества можно либо поместить в отдельную часть ( [math]lbrace
brace[/math] способами), либо поместить его в некоторое подмножество ( [math]k[/math] [math]lbrace
brace[/math] способами, поскольку каждый из [math]lbrace
brace[/math] способов распределения первых [math]n-1[/math] элементов по [math]k[/math] непустым частям дает [math]k[/math] подмножеств, с которыми можно объединить последний элемент).

[math]egin n \ k end = egin kegin n-1 \ k end + egin n-1 \ k-1 end, 0lt klt n \ 0, k = 0 \ 0, n = 0 \ 0, k gt n \ 1, k = n end [/math]

Таблица значений [ править ]

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

Частные случаи [ править ]

[math]lbrace
brace[/math] [math] = 0[/math]

[math]lbrace<0atop k>
brace[/math] [math]= 0[/math]

[math]lbrace
brace [/math] [math]= 1[/math]

Свойства [ править ]

[math]lbrace
brace = sum_^n inom extstyle lbrace
brace[/math]
[math]m![/math] [math]lbrace
brace = sum_^n inom[/math] [math] k^n(-1)^[/math]

[math]left lbrack
ight
brack = lbrace<-natop -k>
brace[/math] , [math]n,k in mathbb[/math] , где [math]left lbrack
ight
brack[/math] — число Стирлинга первого рода

[math]sum limits_^n lbrace
brace = B_n[/math] , где [math]B_n[/math] — число Белла (число всех неупорядоченных разбиений n-элементного множества)

Применения [ править ]

Пусть дано множество из [math]k[/math] элементарных исходов (все исходы равновероятны). Вероятность того, что после [math]n[/math] проведенных экспериментов каждое событие произойдет хотя бы один раз, может быть найдена по следующей формуле: [math]P = [/math] [math]lbrace
brace >[/math]

[math]lbrace
brace[/math] — количество наборов из [math]k[/math] попарно непересекающихся подмножеств исходного множества [math]<1,2, dots ,n>[/math] . Например, [math]lbrace<4atop 3>
brace[/math] [math] = 6[/math] , так как всего шесть наборов из двух непересекающихся подмножеств множества [math]<1,2,3>[/math] : [math]<(1)(23)>,<(12)(3)>, <(13)(2)>, <(1)(2)>, <(1)(3)>, <(2)(3)>[/math] .

Обозначим как [math]lbrace
brace^d[/math] количество всех способов разбиений множества [math]n[/math] натуральных чисел на [math]k[/math] подмножеств, в которых расстояния между двумя любыми элементами [math]i[/math] , [math]j[/math] не меньше [math]d[/math] [math](|i-j| geqslant d)[/math] . Тогда [math]lbrace
brace^d = lbrace
brace,[/math] [math] n geqslant k geqslant d[/math]

Также числа Стирлинга II рода можно определить как коэффициенты в разложении обычных степеней на факториальные: [math]x^n = sum limits_^n extstyle lbrace
brace x^<underline> = sum limits_^n extstyle lbrace
brace (-1)^ x^<overline>[/math] , где [math]x^<underline> = xcdot (x-1)cdot ldotscdot (x-k+1)[/math] — убывающий факториал, [math]x^<overline> = xcdot (x+1)cdot ldotscdot (x+k-1)[/math] — возрастающий факториал. См. также связь между числами Стирлинга.

Переход от базиса обычных степеней к базису убывающих факториальных степеней [ править ]

Теорема:

Доказательство:

[math] riangleright[/math]

[math]x^<underline>=x^<underline>(x-k)[/math] , отсюда [math]xcdot x^<underline>=x^<underline>+kx^<underline>[/math] , следовательно, [math]xcdot x^<underline>[/math] есть

[math]xsum limits_^n extstyle lbrace
brace x^<underline

>=sum limits_^n extstyle lbrace
brace x^<underline>+sum limits_^n extstyle lbrace
brace kx^<underline>=[/math]

[math]sum limits_^n extstyle lbrace
brace x^<underline

>+sum limits_^n extstyle lbrace
brace kx^<underline>= [/math]

Wikimedia Foundation . 2010 .

Смотреть что такое "Число Стирлинга второго рода" в других словарях:

Число Стирлинга первого рода — Числа Стирлинга первого рода количество перестановок из n предметов, имеющие ровно k циклов. Содержание 1 Определение 2 Рекуррентное соотношение 3 Пример 4 Свойст … Википедия

Числа Стирлинга второго рода — В комбинаторике числом Стирлинга второго рода из n по k, обозначаемым или , называется количество неупорядоченных разбиений n элементного множества на k непустых подмножеств. Содержание 1 Рекуррентная формула … Википедия

Числа стирлинга второго рода — В комбинаторике числом Стирлинга второго рода S(n, k) называется число неупорядоченных разбиений n элементного множества на k непустых подмножеств. Числа Стирлинга второго рода задаются рекуррентным соотношением: S(n,n) = 1, для n ≥ 0, S(n,0) = 0 … Википедия

Числа Стирлинга первого рода — (без знака) количество перестановок порядка n с k циклами. Содержание 1 Определение 2 Рекуррентное соотношение 3 … Википедия

Число Белла — В комбинаторике числом Белла Bn называется число всех неупорядоченных разбиений n элементного множества, при этом по определению полагают B0 = 1. Число Белла можно вычислить как сумму чисел Стирлинга второго рода: Для чисел Белла справедлива… … Википедия

Разбиение множества — Разбиение множества это представление его в виде объединения произвольного количества попарно непересекающихся подмножеств. Разбиение множества … Википедия

Парадокс дней рождения — Парадокс дней рождения это кажущееся парадоксальным утверждение, что вероятность совпадения дней рождения (числа и месяца) хотя бы у двух членов группы из 23 и более человек, превышает 50 %. С практической точки зрения это означает,… … Википедия

Числа Белла — В комбинаторике числом Белла называется число всех неупорядоченных разбиений n элементного множества, при этом по определению полагают . Численные значения Значения чисел Белла для образуют последовательность: 1, 1, 2, 5, 15, 52, 203, 877, 4140,… … Википедия

Ольмеки — Эта статья или раздел нуждается в переработке. Пожалуйста, улучшите статью в соответствии с правилами написания статей. Ольмеки название племени … Википедия

Природный газ — (Natural gas) Природный газ это один из самых распространенных энергоносителей Определение и применение газа, физические и химические свойства природного газа Содержание >>>>>>>>>>>>>>> … Энциклопедия инвестора