36
правок
Изменения
Нет описания правки
:<tex>(x)^{n}=x(x+1)(x+2)\cdots(x+n-1).</tex>
Для ясности рассмотрим пример, при котором <tex>n=3</tex>:
:<tex>(x)^{3}=x(x+1)(x+2)=1 \cdot x^3 + 3 \cdot x^2 + 2 \cdot x</tex>, здесь коэффициенты при <tex>x^k</tex> — это <tex>s(3,k)</tex>, то есть:
:<tex>s(3,3)=1</tex>
:<tex>s(3,2)=3</tex>
:<tex>s(3,1)=2</tex>
=== Рекуррентное соотношение ===
Выведем рекуррентную формулу для вычисления чисел Стирлинга первого рода. Каждое представление <tex>n</tex> элементов в виде <tex>k</tex> циклов либо помещает последний элемент(<tex>n-</tex>ый) в отдельный цикл <tex>s(n-1, k-1)</tex> способами, либо вставляет этот элемент в одно из <tex>s(n-1, k)</tex> циклических представлений первых <tex>(n-1)</tex> элементов. В последнем случае существует <tex>(n-1)</tex> различных способов подобной вставки. Например, при вставке элемента <tex>4</tex> в цикл <tex>[1;2;3]</tex> можно получить только 3 разных цикла: <tex>[1;2;3;4], [1;2;4;3], [1;4;2;3]</tex>. Таким образом, рекуррентность имеет вид:
:<tex>s(n,k)=s(n-1,k-1)+(n-1)*s(n-1,k)</tex> '''Доказательство''' Рассмотрим <tex>s(n+1,k)</tex>::По определению, данному выше: :<tex>(x)^{n+1}=x(x+1)(x+2)\cdots(x+n-1)(x+n) = n(x)^{n}+x(x)^{n}</tex> Заметим, что коэффициенты <tex>(x)^{n+1}</tex> — это <tex>s(n,k)</tex> Аналогично можно сказать, что коэффициенты <tex>n(x)^{n}</tex> — это <tex>ns(n,k)</tex> А коэффициенты <tex>x(x)^{n}</tex> — это <tex>s(n,k-1)</tex>, так как степени при <tex>x</tex> увеличатся на 1, а коэффициенты при этом не изменятся. Так как левая и правая части равенства равны как полиномы, то равны и коэффициенты перед <tex>x^k</tex>, следовательно справедливо равенство::<tex>s(n+1,k)=ns(n,k)+s(n,k-1)</tex> или <tex>s(n,k)=(n-1)s(n-1,k)+ s(n-1,k-1)</tex>
==Числа Стирлинга для малых N и K==
<tex>\sum_{k=0}^n s(n,k) = n!</tex> — конечная сумма.
==См. также==
