Разбиения. Комбинаторные числа Стирлинга и Белла

Пусть card(M) = n и k — число непустых подмножеств, на которые разбивается множество M. Рассмотрим разбиение множества M = {а₁, а₂, а_n}. Обозначим через S(n,k) - число разбиений множества на k (n>0, 0<k≤n) непустых частей, а через B(n) – число всех разбиений множества M(n>0) на непустые части.

Тогда S(n,k) будем называть число способов разбить множество M мощностью n на k непустых множества.

S(0,0) = 1

S(n,0) = 0 n≠1

Числа S(n,k) называются числами Стирлинга.

Числа Стирлинга:

Найдем явную формулу для чисел S(n,k). Каждое разбиение M = E₁ E₂ ... E_k на непустые подмножества можно характеризовать набором чисел (l₁, l₂,....,l_n), где

l₁ — число подмножеств разбиения мощности 1,

l₂ — число подмножеств разбиения мощности 2,

..........................................,