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

Число разбиений 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) = 2 ^{n – 1} – 1 при n > 0. Пусть первый элемент множества всегда помещается в 1-й блок. Это обеспечит отсутствие повторяющихся разбиений, отличающихся лишь порядком. Тогда 2-й блок могут образовывать непустые подмножества множества, состоящего из (n – 1) элементов (их число равно 2 ^{n –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 объектов. Имеется 2 ^{n -1} подмножеств из n – 1 объектов. Поскольку все объекты нельзя поместить в одну часть, то S (n, 2) = .