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

Число разбиений n-элементного множества на k блоков произвольного размера (на k непустых подмножеств) выражается числом Стирлинга второго рода S(n, k) (Джеймс Стирлинг, XVIII в.). Для S(n, k)верны следующие соотношения.

S(n, k)= 0 для k > n.

S(0, 0) = 1 (существует только один способ разбиения пустого множества на нулевое число непустых частей, как и в случае с факториалом 0!=1).

S(n, 0) = 0 при n > 0.

S(n, 1) = 1.

S(n, n) = 1.

S(n, 2) = 2n – 1 – 1 при n > 0. Пусть первый элемент множества всегда помещается в 1-й блок. Это обеспечит отсутствие повторяющихся разбиений, отличающихся лишь порядком. Тогда 2-й блок могут образовывать непустые подмножества множества, состоящего из (n – 1) элементов (их число равно 2n–1 – 1), а оставшиеся элементы также помещаются в 1-й блок.

Пример. Например, существует 7 способов разбиения четырехэлементного множества на две части: {1, 2, 3} È {4}, {1, 2, 4} È {3}, {1, 3, 4} È {2}, {2, 3, 4} È {1}, {1, 2} È {3, 4}, {1, 3} È {2, 4}, {1, 4} È {2, 3}. Поэтому S(4, 2) = 7.

Рассмотрим значения чисел Стирлинга для малых значений k:

1. k = 0. Существует только один способ разбиения пустого множества на нулевое число непустых частей, поэтому S(0, 0) = 1. Для непустого множества нужна по крайней мере хотя бы одна часть, так что S(n, 0) = 0 при n > 0.

2. k = 1. Существует только один способ помещения n элементов в одно-единственное непустое множество, поэтому S(n, 1) = 1 при n > 0. Однако S(0, 1)= 0, так как 0-элементное множество пусто.

3. k = 2. Очевидно, что S(0, 2) = 0. Если множество из n>0 объектов разделено на две непустые части, то одна из этих частей содержит последний объект и некоторое подмножество из n – 1 объектов. Имеется 2n-1 подмножеств из n – 1 объектов. Поскольку все объекты нельзя поместить в одну часть, то S(n, 2) = .

 








Дата добавления: 2015-08-20; просмотров: 1596;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.003 сек.