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

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

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

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

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

2) $S(n,k)=\sum \limits _{j=0}^{n-1}{\binom {n-1}{j}}S(j,k-1)$.

при естественных начальных условиях $S(0,0)=1$, $S(n,0)=0$ при $n>0$ и $S(j,k)=0$ при $k>j$.

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

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

Таблица значений при $0\leq n,k\leq 9$

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

Свойства

• $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 _{i=n-1}^{m-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). СПбГУ ИТМО.