Русская Википедия:Числа Стирлинга второго рода

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

Рекуррентные представления

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

1) <math> S(n, k) = S(n-1, k-1) + k \cdot S(n-1, k) </math> для <math>0 < k \le n</math>.
2) <math> S(n, k) = \sum\limits_{j=0}^{n-1}\binom{n-1}{j}S(j,k-1)</math>.
при естественных начальных условиях <math> S(0, 0) = 1 </math>, <math> S(n, 0) = 0 </math> при <math>n > 0</math> и <math> S(j, k) = 0 </math> при <math>k > j</math>.

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

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

Таблица значений при <math>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> x^n = \sum_{k=0}^n S(n, k) \cdot (x)_k, </math> где <math>(x)_k = x (x-1) \cdots (x-k+1).</math>
  • <math>S(m,n)=\sum^{m-1}_{i=n-1} \binom{m-1}{i}\,S(i,n-1)</math>
  • <math>\sum_{m=0}^n S(n,m) = B_n</math> — число Белла.

См. также

Ссылки

Шаблон:Викиучебник

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Числа_Стирлинга_второго_рода&oldid=11339718