Изменения

{{Определение|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 [Комбинаторные объекты|перестановок]] порядка <texdpi="130">n</tex> с <texdpi="130">k</tex> [[Действие перестановки на набор из элементов, представление в виде циклов|циклами]].Числа Стирлинга I рода обозначаются как <tex dpi="130">s(n,k)</tex> или <tex dpi="170">\left[{n\atop k}}\right]</tex>.

==СоотношенияПример==Числами Стирлинга первого рода (со знаком) <texdpi="130">s(n4, k2)=11</tex> называются коэффициенты многочлена:<math>(x)_{n} = \sum_{k=0}^n s(n,k) x^k,</math>

где Существует <mathtex>(x)_n11 </mathtex> — [httpразбиений перестановки из четырех элементов на два цикла://en.wikipedia.org/wiki/Pochhammer_symbol символ Похгаммера] (убывающий факториал):: <math>(x)_{n}=x(x-1)(x-2)\cdots(x-n+1).</math>

Числа имеют чередующийся знак, а их абсолютные значения, называемые числами Стирлинга первого рода (без знака), задают количество перестановок множества, состоящего из <texdpi="130">n</tex> элементов с <tex>k</tex> циклами.Беззнаковые числа Стирлинга задаются коэффициентами многочлена: <math>(x1)(2; 4; 3)^{n} = \sum_{k=0}^n sqquad (1)(n,k2; 3; 4) x^k,</mathtex>

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

Числа Выведем рекуррентную формулу для вычисления чисел Стирлинга первого рода задаются рекуррентным соотношением::. Каждое представление <tex dpi="130">n</tex> элементов в виде <tex dpi="130">k</tex> циклов либо помещает последний элемент (<tex dpi="130">n-</tex>ый) в отдельный цикл <mathtex dpi="130"> s(0n-1, 0k-1) = 1 </mathtex>способами,:либо вставляет этот элемент в одно из <mathtex dpi="130"> s(n-1, 0k) </tex> циклических представлений первых <tex dpi= 0 "130">(n-1)</mathtex>, для элементов. В последнем случае существует <texdpi="130">(n -1)</tex> 0различных способов подобной вставки. Например, при вставке элемента <tex>4</tex>,:в цикл <mathtex> s(0, k1;2;3) = 0 </mathtex>, для можно получить только <tex> 3 </tex>k разных цикла: <tex dpi="130"> 0(1;2;3;4), (1;2;4;3), (1;4;2;3)</tex>. Таким образом,рекуррентность имеет вид:<p>:для чисел со знаком: <mathtex dpi="130"> s(n, k) = \left \{\begin{array}{ll} s(n-0, 0) = 1, k-1) - \\s(n-1, 0) = 0, & n > 0 \cdot \s(n-10, k) </math> для <math>= 0 < , & k < n.</math>0 \\:для чисел без знака: <math> s(n, k) = s(n-1, k-1) + (n-1) \cdot s(n-1, k) , & n,k > 0 \end{array} \right.</mathtex> для <math>0 < k < n.</mathp>

'''Доказательство''' Рассмотрим <tex dpi="130">s(n+1,k)</tex>::По определению, данному выше: :<tex dpi="130">(x)^{n+1}=Числа Стирлинга для малых N 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">n(x)^{n}</tex> — это <tex dpi="130">ns(n,k)</tex> А коэффициенты <tex dpi="130">x(x)^{n}</tex> — это <tex dpi="130">s(n,k-1)</tex>, так как степени при <tex dpi="130">x</tex> увеличатся на <tex> 1 </tex>, а коэффициенты при этом не изменятся. Так как левая и правая части равенства равны как полиномы, то равны и Kкоэффициенты перед <tex dpi="130">x^k</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> === Таблица значений ===Ниже представлены некоторые Найдём числовые значения чисел Стирлинга<tex>s(n, которые легко подсчитать, используя рекуррентные соотношенияk)</tex> для малых <tex>n</tex> и <tex>k</tex>.

! width="20"| n\k!width="40"| 0!width="40"| 1!width="40"| 2!width="40"| 3!width="40"| 4!width="40"| 5!width="40"| 6!width="40"| 7!width="40"| 8!width="40"| 9|-

| ! 1

| ! 2

| ! 3

| ! 4

| ! 5

| ! 6

| ! 7

| ! 8

| ! 9

==ТождестваПрименение== Равносильное определение получается, если числа Стирлинга задать как коэффициенты в разложении: <tex dpi="130">(x)^{n} = \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>::<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> {{Теорема|statement=Числа Стирлинга I рода образуют матрицу переходов в линейном пространстве полиномов базиса возрастающих факториальных степеней к базису обычных степеней <tex dpi="130"> \forall n \in \mathbb{N} : \quad (x)^{n} = \sum\limits_{k=1}^n s(n,k) x^k</tex>.|proof=Индукция по <tex>n</tex>: '''База''': Для <tex>n = 1</tex>, <tex> (x)^{1} = x^{1} </tex> {{---}} очевидно. '''Переход''': Учитывая, что <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\limits_{k=1}^{n-1} s(n-1,k) x^{k+1} + \sum\limits_{k=1}^{n-1} s(n-1,k) x^k \cdot (n-1) </tex>, Введём <tex> t = k + 1 </tex> для первой суммы <tex>\sum\limits_{t=2}^{n} s(n-1,t-1) x^{t} + \sum\limits_{k=1}^{n-1} s(n-1,k) x^k \cdot (n-1) </tex>

Как уже упоминалось ранееПри <tex> t = 1 , \quad \sum\limits_{t=2}^{n} s(n-1,t-1) x^{t} = 0 </tex>, При <tex> k = n , \quad \sum\limits_{k=1}^{n-1} s(n-1,k) x^k \cdot (n-1) = 0 </tex>. Следовательно, мы можем представить выражение в виде одной суммы: <tex> \sum\limits_{k=1}^{n} (s(n-1,k-1)+(n-1)s(n-1,k)) \cdot x^{k} = \sum\limits_{k=1}^n s(n,k) x^k</tex> }}

<tex>s(0,0)=1</tex>=Дополнительные тождества==

#<texdpi="160">s\left[{n\atop 1}\right]=(n-1)!</tex>#:Зафиксируем один элемент, и переставим оставшиеся всеми возможными способами. Повторений не будет, так как чтобы зафиксированный элемент совпал, нужно сдвинуть всю перестановку на <tex dpi = "160">n</tex>, но тогда мы получим исходную перестановку.#<tex dpi="160">\left[{n\atop n}\right]=1</tex>, очевидно#<tex dpi="160">\left[{n\atop n-1}\right]={n \choose 2}</tex>#:Разбить <tex dpi = "160">n</tex> элементов на <tex dpi = "160">n-1</tex> множество можно только одним образом,а именно на множества состоящие из одного элемента и одно множество состоящее из двух. Так как нас интересуют только циклы, получаем выборку двух элементов из всех элементов(множество состоящее из двух элементов всегда является циклом).#<tex dpi="160">\left[{n\atop n-2}\right]=\frac{1}{4} (3n-1){n \choose 3}</tex>#:По аналогии с предыдущим тождеством получаем, что нас интересуют виды конкатенации множеств <tex dpi ="160">((n-4)*1+2+2), ((n-3)*1+3)</tex>. Тогда искомая формула получается упрощением выражения <tex dpi = "160">2! \times {n \choose 3} + \frac{{n \choose 2} \times {n-2 \choose 2}}{2!}</tex>, которая учитывает фиксацию элемента в трехэлементном множестве и повторения двухэлементных.#<tex dpi="160">\left[{n\atop n-3}\right]={n \choose 2}{n \choose 4}</tex>#:Аналогично, учитываем только интересующие нас множества и получаем формулу <tex dpi = "160">2! \times {n \choose 2}{n-2 \choose 3} + \frac{{n \choose 2} \times {n-2 \choose 2} \times {n-4 \choose 2}}{3!} + 3! \times {n \choose 4}={n \choose 2}{n \choose 4}</tex>.

Для целых, положительных <tex>l,m,n:</tex>#<tex dpi="160">\left[{n+1\atop m+1}\right]=\sum\limits_{k=1}^n \left[{n\atop k}\right] {k \choose m}=n! \sum\limits_{k=0}^n \frac{\left[{k\atop m}\right]}{k!} </tex>s#:Второе равенство доказывается путем постепенного спуска вниз: #:<tex dpi="160">\left[{n+1\atop m+1}\right]=\left[{n\atop m}\right] + n \cdot \left[{n\atop m+1}\right]=\left[{n\atop m}\right] + n \cdot \left(\left[{n-1\atop m}\right] + (n-1) \cdot \left[{n-1\atop m+1}\right]\right)=...=\sum\limits_{k=0}^n \left[{k\atop m}\right]\frac{n!}{k!}=n! \sum\limits_{k=0}^n \frac{\left[{k\atop m}\right]}{k!}</tex>#:Чтобы доказать первое, будем использовать биекцию(из прошлого раздела) в факториальные степени,а также формулу <tex dpi="160">(x)_{n+1} = x \cdot (x-1)_n \;</tex>.#:Разложим наше искомое выражение, используя формулу для факториальных степеней, и применив бином Ньютона для второго множителя. Тогда: <tex dpi="160">(x)_{n +1}=\sum_{i=0}^{n}\sum_{k=0}^{i} \left[{n\atop i}\right]\binom{i}{k} x^{k+1}</tex>. Немного преобразовав, получим: <tex dpi="160">(x)_{n+1}=\sum_{k=0}^{n}\sum_{i=k}^{n} \left[{n\atop i}\right]\binom{i}{k} x^{k+1} \;</tex>#:C другой стороны: <tex dpi="160">(x)_{n+1}=\sum_{k=0}^{n+1} \left[{n+1\atop k}\right] x^k = \sum_{k=0}^{n} \left[{n+1\atop k+1}\right] x^{k+1}</tex>#:Приравниваем эти два выражения и получаем искомую формулу.#<tex dpi="160">\left[{n\atop m}\right]=\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\limits_{k=0}^m (n+k) \left[{n+k\atop k}\right]</tex>#:Постепенно раскладываем и получаем искомую формулу:#:<tex dpi="160">\left[{m+n+1\atop m}\right]=\left[{m+n\atop m-1}\right]+\left[{m+n\atop m}\right]\cdot(m+n)=\left[{m+n-1\atop m-2}\right]+\left[{m+n\atop m}\right]\cdot(m+n)+\left[{m+n-1\atop m-1}\right]\cdot(m+n-1)=...=\sum\limits_{k=0}^m (n+k) \left[{n+k\atop k}\right]</tex>

==Связь между числами Стирлинга==Если числа Стирлинга I рода позволяют перейти от базиса <texdpi="130">s(n,n-2x)=\frac^{1},(x)^{42} ,(3n-1x) ^{n \choose 3}\dots </tex>к базису <tex dpi="130">1,x,x^2 \dots </tex>,

то [[Числа Стирлинга второго рода|числа Стирлинга II рода]] играют обратную роль и позволяют перейти от базиса <texdpi="130">1,x,x^2 \dots </tex> к базису <tex dpi="130">s(nx)^{1},n-3(x)=^{n \choose 2},(x)^{n 3} \choose 4}dots </tex>

: <tex>s(n,2)=(n-1)! H_{n-1}</tex>, где <tex>H_{n}</texp> — гармоническое число([http://en.wikipedia.org/wiki/Harmonic_number Harmonic number])

<texdpi="130">s(n,3)=\sum\fraclimits_{k=1}{2} ^n S(n-1,k) s(k,m)! \left[ (H_{n-1})^2 {k- H_m} = \left \{\begin{n-1array}^{(2)ll} 1, & n=m \\right]</tex>0, где <tex>H_& \text{notherwise}^\end{(2)array}\right.</tex> — обобщенное гармоническое число([http:<//en.wikipedia.org/wiki/Harmonic_number#Generalized_harmonic_numbers Generalized harmonic number])p>

==Ссылки==* [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Комбинаторика для программистов 1988, ISBN 5-03-000979-5 {{---}} 49-50 с.80 Числа Стирлинга первого рода]

* [http[Категория: Дискретная математика и алгоритмы]][[Категория://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind Stirling numbers of the first kindКомбинаторика]]