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

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

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

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

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

2) $S(n,k)=\underset{j=0}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{j})S(j,k-<!--\; -\; -->1)$$S(n,k)=\sum \limits _{j=0}^{n-1}{\binom {n-1}{j}}S(j,k-1)$ .

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

Явная формулаПравить

$S(n,k)=\frac{1}{k!}\underset{j=0}{\overset{k}{\sum <!--\; \sum \; -->}}(-<!--\; -\; -->1{)}^{k+j}(\genfrac{}{}{0ex}{}{k}{j})j^n.$$S(n,k)={\frac {1}{k!}}\sum \limits _{{j=0}}^{k}(-1)^{{k+j}}{\binom {k}{j}}j^{n}.$ 

Таблица значений при $0\le <!--\; \le \; -->n,k\le <!--\; \le \; -->9$$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=\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}S(n,k)\cdot <!--\; \cdot \; -->(x{)}_k,$$x^{n}=\sum _{{k=0}}^{n}S(n,k)\cdot (x)_{k},$  где $(x{)}_k=x(x-<!--\; -\; -->1)\cdots <!--\; \cdots \; -->(x-<!--\; -\; -->k+1).$$(x)_{k}=x(x-1)\cdots (x-k+1).$ 
• $S(m,n)=\underset{i=n-<!--\; -\; -->1}{\overset{m-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{m-<!--\; -\; -->1}{i})S(i,n-<!--\; -\; -->1)$$S(m,n)=\sum _{{i=n-1}}^{{m-1}}{\binom {m-1}{i}}\,S(i,n-1)$ 
• $\underset{m=0}{\overset{n}{\sum <!--\; \sum \; -->}}S(n,m)=B_n$$\sum _{{m=0}}^{n}S(n,m)=B_{n}$  — число Белла.

См. такжеПравить

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

СсылкиПравить

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