84
правки
Изменения
Нет описания правки
'''Числа Стирлинга первого рода''' (англ. ''Stirling numbers of the first kind'') — количество [[Комбинаторные объекты|перестановок]] порядка <tex dpi="130">n</tex> с <tex dpi="130">k</tex> [[Действие перестановки на набор из элементов, представление в виде циклов|циклами]]. Числа Стирлинга I рода обозначаются как <tex dpi="130">s(n,k)</tex> или <tex dpi="130170">\left[{n\atop k}\right]</tex>.
==Пример==
<tex dpi="130">s(4,2)=11</tex>
Существует <tex> 11 </tex> разбиений перестановки из четырех элементов на два цикла:
<tex dpi="130">(1)(2; 4; 3) \qquad (1)(2; 3; 4)</tex> <br\>
Числа Стирлинга первого рода задаются рекуррентным соотношением:
Выведем рекуррентную формулу для вычисления чисел Стирлинга первого рода. Каждое представление <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+1,k)</tex>:
:По определению, данному выше:
:<tex dpi="130">(x)^{n+1}=x(x+1)(x+2)...\dots (x+n-1)(x+n) = n(x)^{n}+x(x)^{n}</tex>
Заметим, что коэффициенты <tex dpi="130">(x)^{n+1}</tex> — это <tex dpi="130">s(n+1,k)</tex>
==Применение==
Равносильное определение получается, если числа Стирлинга задать как коэффициенты в разложении: <tex dpi="130">(x)^{n} = \sum_sum\limits_{k=1}^n s(n,k) x^k,</tex>
Следовательно, числа Стирлинга I рода позволяют перейти от базиса <tex dpi="130">(x)^{1},(x)^{2},(x)^{3}...\dots </tex> к базису <tex dpi="130">1,x,x^2 ...\dots </tex> (одно из основных применений)
Здесь <tex dpi="130">(x)^{n}</tex> обозначим как возрастающие факториальные степени или символ Похгаммера<ref> [http://ru.wikipedia.org/wiki/Символ_Похгаммера | символ Википедия {{---}} Символ Похгаммера]</ref>:
:<tex dpi="130">(x)^{n}=x(x+1)(x+2)...\dots (x+n-1).</tex>
Для ясности рассмотрим пример, при котором <tex>n=3</tex>:
{{Теорема
|statement=
Числа Стирлинга I рода образуют матрицу переходов в линейном пространстве полиномов базиса возрастающих факториальных степеней к базису обычных степеней <tex dpi="130"> \forall n \in \mathbb{N} : \quad (x)^{n} = \sum_sum\limits_{k=1}^n s(n,k) x^k</tex>.
|proof=
Индукция по <tex>n</tex>:
<tex> (x)^{n} = (x)^{n-1} \cdot (x+n-1) = x \cdot (x)^{n-1} + (n-1) \cdot (x)^{n-1} = </tex> <tex> \sum_sum\limits_{k=1}^{n-1} s(n-1,k) x^{k+1} + \sum_sum\limits_{k=1}^{n-1} s(n-1,k) x^k \cdot (n-1) </tex>,
Введём <tex> t = k + 1 </tex> для первой суммы
<tex>\sum_sum\limits_{t=2}^{ n} s(n-1,t-1) x^{t} + \sum_sum\limits_{k=1}^{n-1} s(n-1,k) x^k \cdot (n-1) </tex>
При <tex> t = 1 , \quad \sum_sum\limits_{t=2}^{n} s(n-1,t-1) x^{t} = 0 </tex>,
При <tex> k = n , \quad \sum_sum\limits_{k=1}^{n-1} s(n-1,k) x^k \cdot (n-1) = 0 </tex>.
Следовательно, мы можем представить выражение в виде одной суммы:
<tex> \sum_sum\limits_{k=1}^{n} (s(n-1,k-1)+(n-1)s(n-1,k)) \cdot x^{k} = \sum_sum\limits_{k=1}^n s(n,k) x^k</tex>
}}
Для целых, положительных <tex>l,m,n:</tex>
:<tex dpi="160">\left[{n+1\atop m+1}\right]=\sum_sum\limits_{k=1}^n \left[{n\atop k}\right] {k \choose m}=n! \sum_sum\limits_{k=0}^n \left[{k\atop m}\right]/k! </tex>:<tex dpi="160">\left[{n\atop m}\right]=\sum_sum\limits_{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_sum\limits_{k=0}^n (n+k) \left[{n+k\atop k}\right]</tex>
==Связь между числами Стирлинга==
Если числа Стирлинга I рода позволяют перейти от базиса <tex dpi="130">(x)^{1},(x)^{2},(x)^{3} ...\dots </tex> к базису <tex dpi="130">1,x,x^2 ...\dots </tex>,
то [[Числа Стирлинга второго рода|числа Стирлинга II рода ]] играют обратную роль и позволяют перейти от базиса <tex dpi="130">1,x,x^2...\dots </tex> к базису <tex dpi="130">(x)^{1},(x)^{2},(x)^{3}...\dots </tex>
Следовательно, числа Стирлинга тесно связаны друг с другом, а их связь выражается формулой:
:<tex dpi="130">\sum_sum\limits_{k=1}^n S(n,k) s(k,m) (-1)^{k-m} = 1</tex>, если <tex dpi="130">n=m</tex>, иначе <tex dpi="130">0</tex>
==См. также==
* [[Числа Стирлинга второго рода]]
* [[Числа Эйлера I и II рода]]
== Примечания ==
* [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind Wikipedia {{---}} Stirling numbers of the first kind]
* Graham, Knuth, and Patashnik: Concrete Mathematics Second Edition 1994 , ISBN 0-201-55802-5{{---}} 257-267 с.
* В. Липский: Комбинаторика для программистов 1988 , ISBN 5-03-000979-5{{---}} 49-50 с.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
