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

Числа Стирлинга второго рода (англ. stirling numbers of the second kind) — количество способов разбиения множества из $n$ элементов на $k$ непустых подмножеств. Числа Стирлинга II рода обозначаются как $S(n,k)$ или $\lbrace{n\atop k}\rbrace$.

Пример

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

$\{1,2,3\}\{4\} \qquad \{1,2\}\{3,4\}$

$\{1,2,4\}\{3\} \qquad \{1,3\}\{2,4\}$

$\{1,3,4\}\{2\} \qquad \{1,4\}\{2,3\}$

$\{2,3,4\}\{1\}$

Следовательно, $\lbrace{4\atop 2}\rbrace$$= 7$.

Вычисление

Рекуррентное соотношение

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

$\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}$

Таблица значений

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

Частные случаи

$\lbrace{n\atop 0}\rbrace$ $= 0$

$\lbrace{0\atop k}\rbrace$ $= 0$

$\lbrace{n\atop n}\rbrace$$= 1$

$\lbrace{n\atop n-1}\rbrace = \binom{n}{2}$

$\lbrace{n\atop 2}\rbrace = \frac{ \frac11 (2^{n-1}-1^{n-1}) }{0!} \\[8pt] \lbrace{n\atop 3}\rbrace = \frac{ \frac11 (3^{n-1}-2^{n-1})- \frac12 (3^{n-1}-1^{n-1}) }{1!} \\[8pt] \lbrace{n\atop 4}\rbrace = \frac{ \frac11 (4^{n-1}-3^{n-1})- \frac22 (4^{n-1}-2^{n-1}) + \frac13 (4^{n-1}-1^{n-1})}{2!} \\[8pt] \lbrace{n\atop 5}\rbrace = \frac{ \frac11 (5^{n-1}-4^{n-1})- \frac32 (5^{n-1}-3^{n-1}) + \frac33 (5^{n-1}-2^{n-1}) - \frac14 (5^{n-1}-1^{n-1}) }{3!} \\[8pt] {}\ \ \vdots$

Свойства

• $\lbrace{n+1\atop m+1}\rbrace = \sum_{k=0}^n \binom{n}{k} \textstyle \lbrace{k\atop m}\rbrace$
• $m!$$\lbrace{n\atop m}\rbrace = \sum_{k=0}^n \binom{m}{k}$$k^n(-1)^{m-k}$

• $\left \lbrack{n\atop k} \right \rbrack = \lbrace{-n\atop -k}\rbrace$, $n,k \in \mathbb{Z}$, где $\left \lbrack{n\atop k} \right \rbrack$ — число Стирлинга первого рода

• $\sum_{k=0}^n \lbrace{n\atop k}\rbrace = B_n$, где $B_n$ — число Белла (число всех неупорядоченных разбиений n-элементного множества)

Применения

• Пусть дано множество из $k$ элементарных исходов (все исходы равновероятны). Вероятность того, что после $n$ проведенных экспериментов каждое событие произойдет хотя бы один раз, может быть найдена по следующей формуле:$P =$$\lbrace{n\atop k}\rbrace {k! \over{k^n}}$

• $\lbrace{n+1\atop k+1}\rbrace$ — количество наборов из $k$ попарно непересекающихся подмножеств исходного множества $\{1,2...n\}$. Например, $\lbrace{4\atop 3}\rbrace$$= 6$, так как всего шесть наборов из двух непересекающихся подмножеств множества $\{1,2,3\}$: $\{(1)(23)\},\{(12)(3)\}, \{(13)(2)\}, \{(1)(2)\}, \{(1)(3)\}, \{(2)(3)\}$.

• Обозначим как $\lbrace{n\atop k}\rbrace^d$ количество всех способов разбиений множества $n$ натуральных чисел на $k$ подмножеств, в которых расстояния между двумя любыми элементами $i$, $j$ не меньше $d$ $(|i-j| \geq d)$. Тогда $\lbrace{n\atop k}\rbrace^d = \lbrace{n-d+1\atop k-d+1}\rbrace,$$n \geq k \geq d$

• Также числа Стирлинга II рода можно определить как коэффициенты в разложении обычных степеней на факториальные: $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}}$, где $x^{\underline{k}} = x\cdot (x-1)\cdot \ldots\cdot (x-k+1)$ — убывающий факториал, $x^{\overline{k}} = x\cdot (x+1)\cdot \ldots\cdot (x+k-1)$ — возрастающий факториал. См. также связь между числами Стирлинга.

Утверждение:

Числа Стирлинга II рода образуют матрицу переходов в линейном пространстве полиномов от базиса обычных степеней к базису убывающих факториальных степеней.

$\triangleright$

$x^{\underline{k+1}}=x^{\underline{k}}(x-k)$, отсюда $x\cdot x^{\underline{k}}=x^{\underline{k+1}}+kx^{\underline{k}}$, следовательно, $x\cdot x^{\underline{n-1}}$ есть: <tex dpi = "150">x\sum_{k=0}^n \textstyle \lbrace{n-1\atop k}\rbrace x^{\underline{k

$\triangleleft$

=\sum_{k=0}^n \textstyle \lbrace{n-1\atop k}\rbrace x^{\underline{k+1}}+\sum_{k=0}^n \textstyle \lbrace{n-1\atop k}\rbrace kx^{\underline{k}}=\sum_{k=0}^n \textstyle \lbrace{n-1\atop k-1}\rbrace x^{\underline{k}}+\sum_{k=0}^n \textstyle \lbrace{n-1\atop k}\rbrace kx^{\underline{k}}=\sum_{k=0}^n \textstyle (k\lbrace{n-1\atop k}\rbrace + \lbrace{n-1\atop k-1}\rbrace )x^{\underline{k}}=\sum_{k=0}^n \textstyle \lbrace{n\atop k}\rbrace x^{\underline{k}}

}}

Источники информации

• Wikipedia — Stirling numbers of the second kind
• OEIS
• Р. Грэхем, Д. Кнут, О. Паташник Конкретная математика. Основание информатики.—М.:Мир, 1998.—с. 288.— ISBN 5-03-001793-3