Просмотр кода страницы Числа Стирлинга второго рода

{{Другие значения|Числа Стирлинга}}
В [[комбинаторика|комбинаторике]] '''числом Стирлинга второго рода''' из ''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> ===
{| class="wikitable"
 !width="20"| n\k
 !width="40"| 0
 !width="40"| 1
 !width="40"| 2
 !width="40"| 3
 !width="40"| 4
 !width="40"| 5
 !width="40"| 6
 !width="40"| 7
 !width="40"| 8
 !width="40"| 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> — [[число Белла]].

== См. также ==
* [[Число Стирлинга первого рода]]
* [[Число Белла]]

== Ссылки ==
{{Викиучебник|Программное вычисление чисел Стирлинга второго рода|Программное вычисление чисел Стирлинга второго рода}}

* {{MathWorld |urlname=StirlingNumberoftheSecondKind |title=Stirling Number of the Second Kind}}
* Д. Белешко [https://web.archive.org/web/20090502055852/http://rain.ifmo.ru/cat/view.php/theory/combinations/combinations2-2004 Комбинаторика (часть 2)]. СПбГУ ИТМО.

[[Категория:Целочисленные последовательности|С]]
[[Категория:Комбинаторика]]