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

Числа Стирлинга второго рода [math]\begin{Bmatrix} n\\ k \end{Bmatrix}[/math] — количество способов разбиения множества из n элементов на k непустых подмножеств.

Например, существует семь способов разбиения четырехэлементного множества на две части:

[math]\{1,2,3\}\{4\}[/math]

[math]\{1,2,4\}\{3\}[/math]

[math]\{1,3,4\}\{2\}[/math]

[math]\{2,3,4\}\{1\}[/math]

[math]\{1,2\}\{3,4\}[/math]

[math]\{1,3\}\{2,4\}[/math]

[math]\{1,4\}\{2,3\}[/math]

Следовательно, [math]\begin{Bmatrix} 4 \\ 2 \end{Bmatrix} = 7[/math]

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

Если задано множество из n элементов, которое необходимо разбить на k непустых частей, то последний элемент исходного множества можно либо поместить в отдельную часть([math]\begin{Bmatrix} n-1 \\ k-1 \end{Bmatrix}[/math] способами), либо поместить его в некоторое подмножество ([math]k\begin{Bmatrix} n-1 \\ k \end{Bmatrix}[/math] способами, поскольку каждый из [math]\begin{Bmatrix} n-1 \\ k \end{Bmatrix}[/math] способов распределения первых n-1 элементов по k непустым частям дает k подмножеств, с которыми можно объединить последний элемент)

[math]\begin{Bmatrix} n \\ k \end{Bmatrix} = \begin{cases} k\begin{Bmatrix} n-1 \\ k \end{Bmatrix} + \begin{Bmatrix} n-1 \\ k-1 \end{Bmatrix}, 0\lt k\lt n \\ 0, k = 0 \\ 0, n = 0 \\ 0, k \gt n \\ 1, k = n \end{cases} [/math]

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

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

Свойства

• [math]x^n = \sum_{k=0}^n \textstyle \lbrace{n\atop k}\rbrace x^{\underline{k}} = \sum_{k=0}^n \textstyle \lbrace{n\atop k}\rbrace (-1)^{n-k} x^{\overline{k}}[/math], где [math]x^{\underline{k}} = x\cdot (x-1)\cdot \ldots\cdot (x-k+1)[/math] — убывающий факториал, [math]x^{\overline{k}} = x\cdot (x+1)\cdot \ldots\cdot (x+k-1)[/math] — возрастающий факториал.

• [math] \textstyle \lbrace{n+1\atop m+1}\rbrace = \sum_{k=0}^n \binom{n}{k} \textstyle \lbrace{k\atop m}\rbrace[/math]

• [math] m!\textstyle \lbrace{n\atop m}\rbrace = \sum_{k=0}^n \binom{m}{k} k^n(-1)^{m-k}[/math]

• [math]\left \lbrack{n\atop k} \right \rbrack = \textstyle \lbrace{-n\atop -k}\rbrace[/math], [math]n,k \in \mathbb{Z}[/math]