Изменения

{{Определение|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>n</tex> элементов на <tex>k</tex> не пустых подмножеств, при этом две перестановки считаются различными, если хотя бы одно подмножество из первой перестановки нельзя получить ни из одного подмножества второй перестановки с помощью циклического сдвига. Числа Стирлинга 1-го рода обозначаются как <tex>s(n,k)</tex> или <tex>\left[{n\atop k}}\right]</tex>.

Числами Равносильное определение получается, если числа Стирлинга первого рода (со знаком) <tex>s(n, k)</tex> называются задать как коэффициенты многочленав разложении:<mathtex>(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).</mathtex>

Числа имеют чередующийся знак, а их абсолютные значения, называемые числами Стирлинга первого рода (без знака), задают количество перестановок множества, состоящего из <tex>n</tex> элементов с Здесь <tex>k</tex> циклами.Беззнаковые числа Стирлинга задаются коэффициентами многочлена: <math>(x)^{n} = \sum_{k=0}^n s(n,k) x^k,</mathtex>обозначим как возрастающие факториальные степени:

где <math>(x)^n</math> — символ Похгаммера (возрастающий факториал):: <mathtex>(x)^{n}=x(x+1)(x+2)\cdots(x+n-1).</mathtex>

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