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

В комбинаторике числом Стирлинга второго рода из n по k, обозначаемым $S(n, k)$ или $\textstyle \lbrace{n\atop k}\rbrace$, называется количество неупорядоченных разбиений n-элементного множества на k непустых подмножеств.

Рекуррентная формула

Числа Стирлинга второго рода удовлетворяют рекуррентному соотношению:

$S(n, n) = 1$, для n ≥ 0,

$S(n, 0) = 0$, для n > 0,

$S(0, k) = 0$, для k > 0,

$S(n, k) = S(n-1, k-1) + k \cdot S(n-1, k)$ для $0 < k < n.$

Явная формула

$S(n, k) = \frac{1}{k!}\sum\limits_{j=0}^k(-1)^{k+j}\binom{k}{j}j^n.$

Пример

Начальные значения чисел Стирлинга второго рода приведены в таблице:

n\k	0	1	2	3	4	5	6
0	1	0	0	0	0	0	0
1	0	1	0	0	0	0	0
2	0	1	1	0	0	0	0
3	0	1	3	1	0	0	0
4	0	1	7	6	1	0	0
5	0	1	15	25	10	1	0
6	0	1	31	90	65	15	1

Свойства

• $x^n = \sum_{k=0}^n S(n, k) \cdot (x)_k,$ где $(x)_k = x (x-1) \cdots (x-k+1).$
• $S(m,n)=\sum^{m-1}_{i=n-1} \binom{m-1}{i}\,S(i,n-1)$
• $\sum_{m=0}^n S(n,m) = B_n$ — число Белла.

См. также

• Число Стирлинга первого рода
• Число Белла

Ссылки

Имеется викиучебник по теме
«Программное вычисление чисел Стирлинга второго рода»

• Weisstein, Eric W. Stirling Number of the Second Kind (англ.) на сайте Wolfram MathWorld.
• Д. Белешко Комбинаторика (часть 2). СПбГУ ИТМО.