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