Числа Стирлинга второго рода
В комбинаторике числом Стирлинга второго рода из n по k, обозначаемым [math]\displaystyle{ S(n, k) }[/math] или [math]\displaystyle{ \textstyle \lbrace{n\atop k}\rbrace }[/math], называется количество неупорядоченных разбиений n-элементного множества на k непустых подмножеств.
Рекуррентные представления
Числа Стирлинга второго рода удовлетворяют рекуррентным соотношениям:
- 1) [math]\displaystyle{ S(n, k) = S(n-1, k-1) + k \cdot S(n-1, k) }[/math] для [math]\displaystyle{ 0 \lt k \le n }[/math].
- 2) [math]\displaystyle{ S(n, k) = \sum\limits_{j=0}^{n-1}\binom{n-1}{j}S(j,k-1) }[/math].
- при естественных начальных условиях [math]\displaystyle{ S(0, 0) = 1 }[/math], [math]\displaystyle{ S(n, 0) = 0 }[/math] при [math]\displaystyle{ n \gt 0 }[/math] и [math]\displaystyle{ S(j, k) = 0 }[/math] при [math]\displaystyle{ k \gt j }[/math].
Явная формула
- [math]\displaystyle{ S(n, k) = \frac{1}{k!}\sum\limits_{j=0}^k(-1)^{k+j}\binom{k}{j}j^n. }[/math]
Таблица значений при [math]\displaystyle{ 0\le n, k \le 9 }[/math]
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 |
Свойства
- [math]\displaystyle{ x^n = \sum_{k=0}^n S(n, k) \cdot (x)_k, }[/math] где [math]\displaystyle{ (x)_k = x (x-1) \cdots (x-k+1). }[/math]
- [math]\displaystyle{ S(m,n)=\sum^{m-1}_{i=n-1} \binom{m-1}{i}\,S(i,n-1) }[/math]
- [math]\displaystyle{ \sum_{m=0}^n S(n,m) = B_n }[/math] — число Белла.
См. также
Ссылки
- Weisstein, Eric W. Stirling Number of the Second Kind (англ.) на сайте Wolfram MathWorld.
- Д. Белешко Комбинаторика (часть 2). СПбГУ ИТМО.