=== Рекуррентное соотношение ===
Числа Выведем рекуррентную формулу для вычисления чисел Стирлинга первого рода задаются рекуррентным соотношением. Каждое представление <tex dpi="130">n</tex> элементов в виде <tex dpi="130">k</tex> циклов либо помещает последний элемент (<tex dpi="130">n-</tex>ый) в отдельный цикл <tex dpi="130">s(n-1, k-1)</tex> способами, либо вставляет этот элемент в одно из <tex dpi="130">s(n-1, k)</tex> циклических представлений первых <tex dpi="130">(n-1)</tex> элементов. В последнем случае существует <tex dpi="130">(n-1)</tex> различных способов подобной вставки. Например, при вставке элемента <tex>4</tex> в цикл <tex>(1;2;3)</tex> можно получить только <tex> 3 </tex> разных цикла: <tex dpi="130">(1;2;3;4), (1;2;4;3), (1;4;2;3)</tex>. Таким образом, рекуррентность имеет вид:
<p>
<tex dpi="130">
s(n, k) =\left \{\begin{array}{ll} s(0, 0) = 1 , \\
s(n, 0) = 0, & n > 0 \\
s(0, k) = 0, & k > 0 \\s(n,k) = s(n-1,k-1)+(n-1)s(n-1,k), & n,k > 0 \end{array} \right.
</tex>
</p>
Выведем рекуррентную формулу для вычисления чисел Стирлинга первого рода. Каждое представление <tex dpi="130">n</tex> элементов в виде <tex dpi="130">k</tex> циклов либо помещает последний элемент (<tex dpi="130">n-</tex>ый) в отдельный цикл <tex dpi="130">s(n-1, k-1)</tex> способами, либо вставляет этот элемент в одно из <tex dpi="130">s(n-1, k)</tex> циклических представлений первых <tex dpi="130">(n-1)</tex> элементов. В последнем случае существует <tex dpi="130">(n-1)</tex> различных способов подобной вставки. Например, при вставке элемента <tex>4</tex> в цикл <tex>(1;2;3)</tex> можно получить только 3 разных цикла: <tex dpi="130">(1;2;3;4), (1;2;4;3), (1;4;2;3)</tex>. Таким образом, рекуррентность имеет вид:
:<tex dpi="130">s(n,k)=s(n-1,k-1)+(n-1)s(n-1,k)</tex>
'''Доказательство'''
Аналогично можно сказать, что коэффициенты <tex dpi="130">n(x)^{n}</tex> — это <tex dpi="130">ns(n,k)</tex>
А коэффициенты <tex dpi="130">x(x)^{n}</tex> — это <tex dpi="130">s(n,k-1)</tex>, так как степени при <tex dpi="130">x</tex> увеличатся на <tex> 1</tex>, а коэффициенты при этом не изменятся.
Так как левая и правая части равенства равны как полиномы, то равны и коэффициенты перед <tex dpi="130">x^k</tex>, следовательно справедливо равенство:
Следовательно, числа Стирлинга тесно связаны друг с другом, а их связь выражается формулой:
:<p> <tex dpi="130">\sum\limits_{k=1}^n S(n,k) s(k,m) (-1)^{k-m} = \left \{\begin{array}{ll} 1</tex>, если <tex dpi="130">& n=m \\0, & \text{otherwise} \end{array} \right.</tex>, иначе <tex dpi="130">0</texp>
==См. также==
