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="130">\left[{n\atop k}\right]</tex>.
==Пример==
==Применение==
Равносильное определение получается, если числа Стирлинга задать как коэффициенты в разложении: <tex dpi="130">(x)^{n} = \sum_{k=01}^n s(n,k) x^k,</tex>
Следовательно, числа Стирлинга I рода позволяют перейти от базиса <tex dpi="130">(x)^{1},(x)^{2},(x)^{3}...</tex> к базису <tex dpi="130">1,x,x^2 ...</tex> (одно из основных применений)
Здесь <tex dpi="130">(x)^{n}</tex> обозначим как возрастающие факториальные степени или символ Похгаммера<ref> [http://ru.wikipedia.org/wiki/Символ_Похгаммера | символ Похгаммера]</ref>:
:<tex dpi="130">(x)^{n}=x(x+1)(x+2)...(x+n-1).</tex>
:<tex dpi="130">s(3,2)=3</tex>
:<tex dpi="130">s(3,1)=2</tex>
{{Теорема
|statement=
Числа Стирлинга I рода образуют матрицу переходов в линейном пространстве полиномов базиса возрастающих факториальных степеней к базису обычных степеней <tex dpi="130"> \forall n \in \mathbb{N} : \quad (x)^{n} = \sum_{k=1}^n s(n,k) x^k</tex>.
|proof=
Индукция по <tex>n</tex>:
1) Для <tex>n = 1</tex>, <tex> (x)^{1} = x^{1} </tex> - очевидно.
2) Учитывая, что <tex> (x)^{n} = (x)^{n-1} \cdot (x+n-1) </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_{k=1}^{n-1} s(n-1,k) x^{k+1} + \sum_{k=1}^{n-1} s(n-1,k) x^k \cdot (n-1) </tex>,
Введём <tex> t = k + 1 </tex> для первой суммы
<tex>\sum_{t=2}^{ n} s(n-1,t-1) x^{t} + \sum_{k=1}^{n-1} s(n-1,k) x^k \cdot (n-1) </tex>
При <tex> t = 1 , \quad \sum_{t=2}^{n} s(n-1,t-1) x^{t} = 0 </tex>,
При <tex> k = n , \quad \sum_{k=1}^{n-1} s(n-1,k) x^k \cdot (n-1) = 0 </tex>.
Следовательно, мы можем представить выражение в виде одной суммы:
<tex> \sum_{k=1}^{n} (s(n-1,k-1)+(n-1)s(n-1,k)) \cdot x^{k} = \sum_{k=1}^n s(n,k) x^k</tex>
}}
==Дополнительные тождества==
Если числа Стирлинга I рода позволяют перейти от базиса <tex dpi="130">(x)^{1},(x)^{2},(x)^{3} ...</tex> к базису <tex dpi="130">1,x,x^2 ...</tex>,
то числа Стирлинга 2-го II рода играют обратную роль и позволяют перейти от базиса <tex dpi="130">1,x,x^2...</tex> к базису <tex dpi="130">(x)^{1},(x)^{2},(x)^{3}...</tex>
Следовательно, числа Стирлинга тесно связаны друг с другом, а их связь выражается формулой:
* [[Числа Стирлинга второго рода]]
==СсылкиПримечания ==<references/> ==Источники информации==
* [http://ru.wikipedia.org/wiki/Числа_Стирлинга_первого_рода Википедия {{---}} Числа Стирлинга первого рода]
* [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
* В. Липский: Комбинаторика для программистов 1988 ISBN 5-03-000979-5
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
