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

Число разбиений 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) = .