Изменения

'''Числа Стирлинга первого рода''' (''Stirling numbers of the first kind'') — количество [[Комбинаторные объекты|перестановок]] порядка <texdpi="130">n</tex> с <texdpi="130">k</tex> [[Действие перестановки на набор из элементов, представление в виде циклов|циклами]](или число способов посадить <texdpi="130">n</tex> человек с номерами на майках за <texdpi="130">k</tex> одинаковых круглых столов, чтобы за каждым столом кто-то сидел). Числа Стирлинга 1-го рода обозначаются как <texdpi="130">s(n,k)</tex> или <texdpi="130">\left[{n\atop k}\right]</tex>. Числа Стирлинга используются в задачах(например, олимпиадных), где одной из подзадач является нахождение количества перестановок порядка <texdpi="130">n</tex> с <texdpi="130">k</tex> циклами.

<texdpi="130">s(4,2)=11</tex>

<texdpi="130">(1)(2; 4; 3) \qquad (1)(2; 3; 4)</tex> <br\><texdpi="130">(2)(1; 4; 3) \qquad (2)(1; 3; 4)</tex> <br\><texdpi="130">(3)(1; 4; 2) \qquad (3)(1; 2; 4)</tex> <br\><texdpi="130">(4)(1; 3; 2) \qquad (4)(1; 2; 3)</tex> <br\><texdpi="130">(1; 2)(3; 4)</tex> <br\><texdpi="130">(1; 4)(2; 3)</tex> <br\><texdpi="130">(1; 3)(2; 4)</tex> <br\>

Заметим, что перестановки <texdpi="130">(1)(2; 3; 4)</tex> и <texdpi="130">(1)(2; 4; 3)</tex> считаются различными, так как подмножество <texdpi="130">(2; 3; 4)</tex> невозможно получить ни из подмножества <texdpi="130">(1)</tex>, ни из подмножества <texdpi="130">(2; 4; 3)</tex> с помощью циклического сдвига элементов.

Равносильное определение получается, если числа Стирлинга задать как коэффициенты в разложении: <texdpi="130">(x)^{n} = \sum_{k=0}^n s(n,k) x^k,</tex>

Следовательно, числа Стирлинга 1-го рода позволяют перейти от базиса <texdpi="130">(x)^{1},(x)^{2},(x)^{3} \cdots</tex> к базису <texdpi="130">1,x,x^2 \cdots</tex>

Здесь <texdpi="130">(x)^{n}</tex> обозначим как возрастающие факториальные степени:

:<texdpi="130">(x)^{n}=x(x+1)(x+2)\cdots(x+n-1).</tex>

:<texdpi="130">(x)^{3}=x(x+1)(x+2)=1 \cdot x^3 + 3 \cdot x^2 + 2 \cdot x</tex>, здесь коэффициенты при <texdpi="130">x^k</tex> — это <texdpi="130">s(3,k)</tex>, то есть::<texdpi="130">s(3,3)=1</tex> :<texdpi="130">s(3,2)=3</tex> :<texdpi="130">s(3,1)=2</tex>

:<texdpi="130"> s(0, 0) = 1 </tex>,:<texdpi="130"> s(n, 0) = 0 </tex>, для <texdpi="130">n > 0</tex>,:<texdpi="130"> s(0, k) = 0 </tex>, для <texdpi="130">k > 0</tex>.

Выведем рекуррентную формулу для вычисления чисел Стирлинга первого рода. Каждое представление <texdpi="130">n</tex> элементов в виде <texdpi="130">k</tex> циклов либо помещает последний элемент(<texdpi="130">n-</tex>ый) в отдельный цикл <texdpi="130">s(n-1, k-1)</tex> способами, либо вставляет этот элемент в одно из <texdpi="130">s(n-1, k)</tex> циклических представлений первых <texdpi="130">(n-1)</tex> элементов. В последнем случае существует <texdpi="130">(n-1)</tex> различных способов подобной вставки. Например, при вставке элемента <tex>4</tex> в цикл <tex>[1;2;3]</tex> можно получить только 3 разных цикла: <texdpi="130">[1;2;3;4], [1;2;4;3], [1;4;2;3]</tex>. Таким образом, рекуррентность имеет вид::<texdpi="130">s(n,k)=s(n-1,k-1)+(n-1)s(n-1,k)</tex>

Рассмотрим <texdpi="130">s(n+1,k)</tex>:

:<texdpi="130">(x)^{n+1}=x(x+1)(x+2)\cdots(x+n-1)(x+n) = n(x)^{n}+x(x)^{n}</tex>

Заметим, что коэффициенты <texdpi="130">(x)^{n+1}</tex> — это <texdpi="130">s(n+1,k)</tex>

Аналогично можно сказать, что коэффициенты <texdpi="130">n(x)^{n}</tex> — это <texdpi="130">ns(n,k)</tex>

А коэффициенты <texdpi="130">x(x)^{n}</tex> — это <texdpi="130">s(n,k-1)</tex>, так как степени при <texdpi="130">x</tex> увеличатся на 1, а коэффициенты при этом не изменятся.

Так как левая и правая части равенства равны как полиномы, то равны и коэффициенты перед <texdpi="130">x^k</tex>, следовательно справедливо равенство::<texdpi="130">s(n+1,k)=ns(n,k)+s(n,k-1)</tex> или <texdpi="130">s(n,k)=(n-1)s(n-1,k)+ s(n-1,k-1)</tex>

==Тождества, включающие числа Стирлинга первого родаДополнительные тождества==

:<texdpi = "160">s(\left[{0,\atop 0)}\right]=1</tex>

:<texdpi = "160">s(\left[{n,\atop 0)}\right]=s(\left[{0,\atop k)}\right]=0</tex>, в общем случае <texdpi = "160">s(\left[{n,\atop k)}\right]=0</tex>, если <tex>k > n</tex>

:<texdpi="160">s(\left[{n,\atop 1)}\right]=(n-1)!</tex>

:<texdpi="160">s(\left[{n,\atop n)}\right]=1</tex>

:<texdpi="160">s(\left[{n,\atop n-1)}\right]={n \choose 2}</tex>

:<texdpi="160">s(\left[{n,\atop n-2)}\right]=\frac{1}{4} (3n-1) {n \choose 3}</tex>

:<texdpi="160">s(\left[{n,\atop n-3)}\right]={n \choose 2}{n \choose 4}</tex> Для целых, положительных <tex>l,m,n:</tex>:<tex dpi="160">\left[{n+1\atop m+1}\right]=\sum_{k=1}^n \left[{n\atop k}\right] {k \choose m}=n! \sum_{k=0}^n \left[{k\atop m}\right]/k! </tex>:<tex dpi="160">\left[{n\atop m}\right]=\sum_{k=1}^n \left[{n+1\atop k+1}\right] {k \choose m} (-1)^{m-k} </tex>:<tex dpi="160">\left[{m+n+1\atop m}\right]=\sum_{k=0}^n (n+k) \left[{n+k\atop k}\right]</tex>

Если числа Стирлинга 1-го рода позволяют перейти от базиса <texdpi="130">(x)^{1},(x)^{2},(x)^{3} \cdots</tex> к базису <texdpi="130">1,x,x^2 \cdots</tex>,

то числа Стирлинга 2-го рода играют обратную роль и позволяют перейти от базиса <texdpi="130">1,x,x^2 \cdots</tex> к базису <texdpi="130">(x)^{1},(x)^{2},(x)^{3} \cdots</tex>.

:<texdpi="130">\sum_{k=1}^n S(n,k) s(k,m) (-1)^{k-m} = 1</tex>, если <texdpi="130">n=m</tex>, иначе <texdpi="130">0</tex>