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

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

Рекуррентные представления

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

1) [math]\displaystyle{ S(n, k) = S(n-1, k-1) + k \cdot S(n-1, k) }[/math] для [math]\displaystyle{ 0 \lt k \le n }[/math].

2) [math]\displaystyle{ S(n, k) = \sum\limits_{j=0}^{n-1}\binom{n-1}{j}S(j,k-1) }[/math].

при естественных начальных условиях [math]\displaystyle{ S(0, 0) = 1 }[/math], [math]\displaystyle{ S(n, 0) = 0 }[/math] при [math]\displaystyle{ n \gt 0 }[/math] и [math]\displaystyle{ S(j, k) = 0 }[/math] при [math]\displaystyle{ k \gt j }[/math].

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

[math]\displaystyle{ S(n, k) = \frac{1}{k!}\sum\limits_{j=0}^k(-1)^{k+j}\binom{k}{j}j^n. }[/math]

Таблица значений при [math]\displaystyle{ 0\le n, k \le 9 }[/math]

n\k	0	1	2	3	4	5	6	7	8	9
0	1
1	0	1
2	0	1	1
3	0	1	3	1
4	0	1	7	6	1
5	0	1	15	25	10	1
6	0	1	31	90	65	15	1
7	0	1	63	301	350	140	21	1
8	0	1	127	966	1701	1050	266	28	1
9	0	1	255	3025	7770	6951	2646	462	36	1

Свойства

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

См. также

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

Ссылки

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