Меню сайта

Статистика

Онлайн всего: 1

Гостей: 1

Пользователей: 0

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

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

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

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

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

Явная формула

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

Пример

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

$S(n, n) = 1$ , для n ≥ 0,

$S(n, 0) = 0$ , для n > 0,

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

n\k	0	1	2	3	4	5	6
0	1	0	0	0	0	0	0
1	0	1	0	0	0	0	0
2	0	1	1	0	0	0	0
3	0	1	3	1	0	0	0
4	0	1	7	6	1	0	0
5	0	1	15	25	10	1	0
6	0	1	31	90	65	15	1

Свойства

$x^n = \sum_{k=0}^n S(n, k) \cdot (x)_k,$ где $(x)_k = x (x-1) \cdots (x-k+1).$
$S(m,n)=\sum^{m-1}_{i=n-1} \binom{m-1}{i}\,S(i,n-1)$
$\sum_{m=0}^n S(n,m) = B_n$ — число Белла.

Вход на сайт

Поиск

Друзья сайта

Официальный блог

Сообщество uCoz

FAQ по системе

Инструкции для uCoz

Разработчики сайта: Иушина Анастасия, Михиенко Дарья. Красноярск, ИМФИ, 2025
Конструктор сайтов — uCoz