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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Рекуррентная формула[править | править вики-текст]

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

 S(n, n) = 1 , для n ≥ 0,
 S(n, 0) = 0 , для n > 0,
 S(0, k) = 0 , для k > 0,
 S(n, k) = S(n-1, k-1) + k \cdot S(n-1, k) для 0 < k < n.

Явная формула[править | править вики-текст]

 S(n, k) = \frac{1}{k!}\sum\limits_{j=0}^k(-1)^{k+j}\binom{k}{j}j^n.

Таблица значений[править | править вики-текст]

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

Свойства[править | править вики-текст]

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]