Изменения
Нет описания правки
'''Числа Стирлинга первого рода''' (''Stirling numbers of the first kind'') — количество [[Комбинаторные объекты|перестановок]] порядка <tex dpi="130">n</tex> с <tex dpi="130">k</tex> [[Действие перестановки на набор из элементов, представление в виде циклов|циклами]](или число способов посадить <tex dpi="130">n</tex> человек с номерами на майках за <tex dpi="130">k</tex> одинаковых круглых столов, чтобы за каждым столом кто-то сидел). Числа Стирлинга 1-го рода обозначаются как <tex dpi="130">s(n,k)</tex> или <tex dpi="130">\left[{n\atop k}\right]</tex>. Числа Стирлинга используются в задачах(например, олимпиадных), где одной из подзадач является нахождение количества перестановок порядка <tex dpi="130">n</tex> с <tex dpi="130">k</tex> циклами.
==Пример==
Заметим, что перестановки <tex dpi="130">(1)(2; 3; 4)</tex> и <tex dpi="130">(1)(2; 4; 3)</tex> считаются различными, так как подмножество <tex dpi="130">(2; 3; 4)</tex> невозможно получить ни из подмножества <tex dpi="130">(1)</tex>, ни из подмножества <tex dpi="130">(2; 4; 3)</tex> с помощью циклического сдвига элементов.
==СоотношенияВычисления==Равносильное определение получается, если числа Стирлинга задать как коэффициенты в разложении: <tex dpi="130">(x)^{n} = \sum_{k=0}^n s(n,k) x^k,</tex> Следовательно, числа Стирлинга 1-го рода позволяют перейти от базиса <tex dpi="130">(x)^{1},(x)^{2},(x)^{3} \cdots</tex> к базису <tex dpi="130">1,x,x^2 \cdots</tex> (одно из основных применений) Здесь <tex dpi="130">(x)^{n}</tex> обозначим как возрастающие факториальные степени: :<tex dpi="130">(x)^{n}=x(x+1)(x+2)\cdots(x+n-1).</tex> Для ясности рассмотрим пример, при котором <tex>n=3</tex>::<tex dpi="130">(x)^{3}=x(x+1)(x+2)=1 \cdot x^3 + 3 \cdot x^2 + 2 \cdot x</tex>, здесь коэффициенты при <tex dpi="130">x^k</tex> — это <tex dpi="130">s(3,k)</tex>, то есть::<tex dpi="130">s(3,3)=1</tex> :<tex dpi="130">s(3,2)=3</tex> :<tex dpi="130">s(3,1)=2</tex>
=== Рекуррентное соотношение ===
:<tex dpi="130">s(n+1,k)=ns(n,k)+s(n,k-1)</tex> или <tex dpi="130">s(n,k)=(n-1)s(n-1,k)+ s(n-1,k-1)</tex>
{|border="1"
| 1
|}
==Представление==
Равносильное определение получается, если числа Стирлинга задать как коэффициенты в разложении: <tex dpi="130">(x)^{n} = \sum_{k=0}^n s(n,k) x^k,</tex>
Следовательно, числа Стирлинга 1-го рода позволяют перейти от базиса <tex dpi="130">(x)^{1},(x)^{2},(x)^{3} \cdots</tex> к базису <tex dpi="130">1,x,x^2 \cdots</tex> (одно из основных применений)
Здесь <tex dpi="130">(x)^{n}</tex> обозначим как возрастающие факториальные степени или символ Похгаммера:
:<tex dpi="130">(x)^{n}=x(x+1)(x+2)\cdots(x+n-1).</tex>
Для ясности рассмотрим пример, при котором <tex>n=3</tex>:
:<tex dpi="130">(x)^{3}=x(x+1)(x+2)=1 \cdot x^3 + 3 \cdot x^2 + 2 \cdot x</tex>, здесь коэффициенты при <tex dpi="130">x^k</tex> — это <tex dpi="130">s(3,k)</tex>, то есть:
:<tex dpi="130">s(3,3)=1</tex>
:<tex dpi="130">s(3,2)=3</tex>
:<tex dpi="130">s(3,1)=2</tex>
==Дополнительные тождества==
==Ссылки==
* [http://ru.wikipedia.org/wiki/Числа_Стирлинга_первого_рода Википедия {{---}} Числа Стирлинга первого рода]
* [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind Wikipedia {{---}} Stirling numbers of the first kind]
== Литература ==
