Тема: разбиения на блоки и циклы
Основные вопросы, рассматриваемые на лекции:
1. Разбиения множества на m блоков.
2. Число Стирлинга второго рода.
3. Разбиения перестановки на m циклов.
4. Число Стирлинга первого рода.
5. Факториальные многочлены.
Краткое содержание лекционного материала
1. Разбиения множества на m блоков. Говорят, что семейство множеств <M1,…,Mk> является разбиением множества M на k блоков M1,…,Mk, если M1,…,Mk – непустые, попарно не пересекающиеся, подмножества множества M и объединение множеств M1,…,Mk есть множества 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 называется числом Белла Bn.
Ясно, что .
Пример 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
Таблица значений [ править ]
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 inomextstyle 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 [math]xsum limits_^n extstyle lbrace brace x^<underline>+sum limits_^n extstyle lbrace brace kx^<underline [math]sum limits_^n extstyle lbrace brace kx^<underline 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) Природный газ это один из самых распространенных энергоносителей Определение и применение газа, физические и химические свойства природного газа Содержание >>>>>>>>>>>>>>> … Энциклопедия инвестора |