Ln - число подмножеств разбиения мощности n

Эти числа удовлетворяют тождеству

1 l₁ + 2 l₂ +.... + n l_n = n.

Теорема 3.

Доказательство.

Процесс построения всех разбиений множества M на k непустых частей, характеризуемых набором чисел (l₁, l₂,...., l_n), l₁ + l₂ +.... + l_n = k, можно представить следующим образом.

Возьмем п упорядоченных ячеек и разобьем их на k; подмножеств, характеризуемых данным набором чисел (l₁, l₂,...., l_n). Эти подмножества занумеруем числами 0, 1,..., k - 1. Разместим в этих ячейках элементы а₁,..., a_п. Очевидно, что разбиение ячеек на подмножества структуры (l₁, l₂,...., l_n) порождает разбиение элементов а₁,..., a_п на подмножества такой же структуры. Последнее задается набором (б₁, б₂,..., б_п), где б_i — номер подмножества разбиения ячеек, которому принадлежит элемент б_i Производя различные размещения элементов а₁,..., a_п, по ячейкам, получим все разбиения множества M на k непустых частей данной структуры (l₁, l₂,...., l_n). При этом два размещения определяют одно и то же разбиение множества M тогда и только тогда, когда для соответствующих им наборов (б₁, б₂,..., б_п) и (б₁, б₂,..., б_п) выполнено условие

Если сравнить соответствующие слагаемые в (15) и (18), то можно увидеть, что они выражают одно и то же число. Отсюда получаем еще одно явное выражение для S(n,r) (n, r>0)

Эта формула не пригодна для практических вычислений S(n,k), так как она предполагает знание всех решений уравнения (14) или (17).

Эффективный способ вычисления чисел Стирлинга 2-го рода и изучение их свойств связано с установлением ряда реккурентных соотношений для S(n,k).

Теорема. S(m,n) = S(m-1,n-1) + n S(m-1,n)

Комбинаторные числа можно изучать двумя способами: теоретико-множественным и алгебраическим.

Числа Стирлинга 2-го рода (Джеймс Стирлинг (1699-1770))

Комбинаторные числа S(n,k) называются числа Стирлинга 2-го рода, а комбинаторные числа B(n) - числами Белла. Эти числа связаны соотношением:

Число разбиений m -элементного множества на n блоков называется числом Стирлинга второго рода и обозначаются S(m,n)

Найдем явную формулу для определения чисел Стирлинга 2-го рода S(n,k).

По определению

S(m,0) = 0 при m > 0

S(m, m) = 1

S(0, 0) = 1

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