Определение
Числа Стирлинга второго рода (Stirling numbers of the second kind) [math]\lbrace{n\atop k}\rbrace[/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]\lbrace{4\atop 2}\rbrace[/math][math] = 7[/math]
Также числа Стирлинга 2-го рода можно определить как коэффициенты в разложении обычных степеней на факториальные:
[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] — возрастающий факториал.
Рекуррентная формула
Если задано множество из n элементов, которое необходимо разбить на k непустых частей, то последний элемент исходного множества можно либо поместить в отдельную часть([math]\lbrace{n-1\atop k-1}\rbrace[/math] способами), либо поместить его в некоторое подмножество ([math]k[/math][math]\lbrace{n-1\atop k}\rbrace[/math] способами, поскольку каждый из [math]\lbrace{n-1\atop k}\rbrace[/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]
Чтобы доказать равносильность двух определений используем метод математической индукции.
- [math]x^0=x^{\underline{0}} = 1[/math]
- предположим, что утверждение верно для некоторого k-1:
[math]x^{k-1} = \sum_{i=0}^{k-1} \textstyle \lbrace{k-1\atop i}\rbrace x^{\underline{i}}[/math]
[math]x^{k} = x\sum_{i=0}^{k-1} \textstyle \lbrace{k-1\atop i}\rbrace x^{\underline{i}} = \sum_{i=0}^{k-1} \textstyle \lbrace{k-1\atop i}\rbrace x^{\underline{i}}(x-i+i) = \sum_{i=0}^{k-1} \textstyle \lbrace{k-1\atop i}\rbrace (x^{\underline{i+1}}+ix^{\underline{i}}) = \sum_{i=0}^k \textstyle \lbrace{k-1\atop i-1}\rbrace x^{\underline{i}}+\sum_{i=0}^k \textstyle \lbrace{k-1\atop i}\rbrace ix^{\underline{i}} = \sum_{i=0}^k (\textstyle \lbrace{k-1\atop i-1}\rbrace + i\textstyle \lbrace{k-1\atop i}\rbrace)x^{\underline{i}} = \sum_{i=0}^k \textstyle \lbrace{k\atop i}\rbrace x^{\underline{i}}[/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]\lbrace{n\atop 0}\rbrace[/math] [math] = 0[/math]
[math]\lbrace{0\atop k}\rbrace[/math] [math]= 0[/math]
[math]\lbrace{n\atop n}\rbrace [/math][math]= 1[/math]
[math]\lbrace{n\atop n-1}\rbrace = \binom{n}{2}[/math]
[math]
\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
[/math]
Свойства
- [math]\lbrace{n+1\atop m+1}\rbrace = \sum_{k=0}^n \binom{n}{k} \textstyle \lbrace{k\atop m}\rbrace[/math]
- [math]m![/math][math]\lbrace{n\atop m}\rbrace = \sum_{k=0}^n \binom{m}{k}[/math][math] k^n(-1)^{m-k}[/math]
- [math]\left \lbrack{n\atop k} \right \rbrack = \lbrace{-n\atop -k}\rbrace[/math], [math]n,k \in \mathbb{Z}[/math], где [math]\left \lbrack{n\atop k} \right \rbrack[/math] — число Стирлинга первого рода
- [math]\sum_{k=0}^n \lbrace{n\atop k}\rbrace = B_n[/math], где [math]B_n[/math] — число Белла (число всех неупорядоченных разбиений n-элементного множества)
Применения
- пусть дано множество из k элементарных исходов (все исходы равновероятны). Вероятность того, что после n проведенных экспериментов каждое событие произойдет хотя бы один раз, может быть найдена по следующей формуле:
[math]P = [/math][math]\lbrace{n\atop k}\rbrace {k! \over{k^n}}[/math]
- [math]\lbrace{n+1\atop k+1}\rbrace[/math] — количество наборов из k попарно непересекающихся подмножеств исходного множества [math]\{1,2...n\}[/math]. Например, [math]\lbrace{4\atop 3}\rbrace[/math][math] = 6[/math], так как всего шесть наборов из двух непересекающихся подмножеств множества [math]\{1,2,3\}[/math]: [math]\{(1)(23)\},\{(12)(3)\}, \{(13)(2)\}, \{(1)(2)\}, \{(1)(3)\}, \{(2)(3)\}[/math]
- обозначим как [math]\lbrace{n\atop k}\rbrace^d[/math] количество всех способов разбиений множества n натуральных чисел на k подмножеств, в которых расстояния между двумя любыми элементами i, j не меньше d [math](|i-j| \geq d)[/math]. Тогда
[math]\lbrace{n\atop k}\rbrace^d = \lbrace{n-d+1\atop k-d+1}\rbrace,[/math][math] n \geq k \geq d[/math]
Источники
- Р. Грэхем, Д. Кнут, О. Паташник Конкретная математика. Основание информатики.—М.:Мир, 1998.—с. 288.— ISBN 5-03-001793-3
