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

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

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

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

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

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

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

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

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

Таблица значений при ${\displaystyle 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

Свойства

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

См. также

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

Ссылки

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