36
правок
Изменения
Нет описания правки
{{В разработкеОпределение|definition='''Числа Стирлинга первого рода''' (''Stirling numbers of the first kind'') — количество [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%BE%D0%BC%D0%B1%D0%B8%D0%BD%D0%B0%D1%82%D0%BE%D1%80%D0%BD%D1%8B%D0%B5_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%8B перестановок] порядка <tex>n</tex> с <tex>k</tex> циклами.}} ==Соотношения==Числами Стирлинга первого рода (со знаком) <tex>s(n, k)</tex> называются коэффициенты многочлена:<math>(x)_{n} = \sum_{k=0}^n s(n,k) x^k,</math> где <math>(x)_n</math> — [http://en.wikipedia.org/wiki/Pochhammer_symbol символ Похгаммера] (убывающий факториал):: <math>(x)_{n}=x(x-1)(x-2)\cdots(x-n+1).</math> Числа имеют чередующийся знак, а их абсолютные значения, называемые числами Стирлинга первого рода (без знака), задают количество перестановок множества, состоящего из <tex>n</tex> элементов с <tex>k</tex> циклами.Беззнаковые числа Стирлинга задаются коэффициентами многочлена: <math>(x)^{n} = \sum_{k=0}^n s(n,k) x^k,</math> где <math>(x)^n</math> — символ Похгаммера (возрастающий факториал):: <math>(x)^{n}=x(x+1)(x+2)\cdots(x+n-1).</math> === Рекуррентное соотношение === Числа Стирлинга первого рода задаются рекуррентным соотношением::<math> s(0, 0) = 1 </math>,:<math> s(n, 0) = 0 </math>, для <tex>n > 0</tex>,:<math> s(0, k) = 0 </math>, для <tex>k > 0</tex>,:для чисел со знаком: <math> s(n, k) = s(n-1, k-1) - (n-1) \cdot s(n-1, k) </math> для <math>0 < k < n.</math>:для чисел без знака: <math> s(n, k) = s(n-1, k-1) + (n-1) \cdot s(n-1, k) </math> для <math>0 < k < n.</math> ==Числа Стирлинга для малых N и K==Ниже представлены некоторые значения чисел Стирлинга, которые легко подсчитать, используя рекуррентные соотношения {| class="wikitable"|-! n\k! 0! 1! 2! 3! 4! 5! 6! 7! 8! 9|-| 0| 1||||||||||-| 1| 0| 1|||||||||-| 2| 0| 1| 1||||||||-| 3| 0| 2| 3| 1|||||||-| 4| 0| 6| 11| 6| 1||||||-| 5| 0| 24| 50| 35| 10| 1|||||-| 6| 0| 120| 274| 225| 85| 15| 1||||-| 7 | 0| 720| 1764| 1624| 735| 175| 21| 1|||-| 8 | 0| 5040| 13068| 13132| 6769| 1960| 322| 28| 1||-| 9 | 0| 40320| 109584| 118124| 67284| 22449| 4536| 546| 36| 1|} ==Тождества, включающие числа Стирлинга первого рода=====Простые тождества=== Как уже упоминалось ранее: <tex>s(0,0)=1</tex> <tex>s(n,0)=s(0,k)=0</tex>, в общем случае <tex>s(n,k)=0</tex>, если <tex>k > n</tex> Также <tex>s(n,1)=(n-1)!</tex> <tex>s(n,n)=1</tex> <tex>s(n,n-1)={n \choose 2}</tex> <tex>s(n,n-2)=\frac{1}{4} (3n-1) {n \choose 3}</tex> <tex>s(n,n-3)={n \choose 2}{n \choose 4}</tex> ===Другие тождества=== <tex>s(n,2)=(n-1)! H_{n-1}</tex>, где <tex>H_{n}</tex> — гармоническое число([http://en.wikipedia.org/wiki/Harmonic_number Harmonic number]) <tex>s(n,3)=\frac{1}{2} (n-1)! \left[ (H_{n-1})^2 - H_{n-1}^{(2)} \right]</tex>, где <tex>H_{n}^{(2)}</tex> — обобщенное гармоническое число([http://en.wikipedia.org/wiki/Harmonic_number#Generalized_harmonic_numbers Generalized harmonic number]) <tex>\sum_{k=0}^n s(n,k) = n!</tex> — конечная сумма. ==См. также==* [[Числа Стирлинга второго рода]] ==Ссылки==* [http://ru.wikipedia.org/w/index.php?title=%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A1%D1%82%D0%B8%D1%80%D0%BB%D0%B8%D0%BD%D0%B3%D0%B0_%D0%BF%D0%B5%D1%80%D0%B2%D0%BE%D0%B3%D0%BE_%D1%80%D0%BE%D0%B4%D0%B0&stable=0#.D0.9F.D1.80.D0.B8.D0.BC.D0.B5.D1.80 Числа Стирлинга первого рода] * [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind Stirling numbers of the first kind]
