Изменения

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

<texdpi="130">s(4,2)=11([1;2][3;4]; [1;4][2;3]; [1;3][2;4]; [1][2;4;3]; [1][2;3;4]; [2][1;4;3]; [2][1;3;4]; [3][1;4;2]; [3][1;2;4]; [4][1;3;2]; [4][1; 2;3])</tex>.

Заметим, что перестановки Существует <tex>[1][2;3;4]11 </tex> и <tex>[1][2;4;3]</tex> считаются различными, так как подмножество <tex>[2;3;4]</tex> невозможно получить ни из подмножества <tex>[1]</tex>, ни разбиений перестановки из подмножества <tex>[2;4;3]</tex> с помощью циклического сдвига четырех элементов. ==Соотношения==Равносильное определение получается, если числа Стирлинга задать как коэффициенты в разложениина два цикла: <tex>(x)^{n} = \sum_{k=0}^n s(n,k) x^k,</tex>

Здесь <texdpi="130">(x1)(2; 4; 3) \qquad (1)(2; 3; 4)^{n}</tex> обозначим как возрастающие факториальные степени:

:<texdpi="130">(x2)^{n}=x(x+1; 4; 3)\qquad (x+2)\cdots(x+n-1; 3; 4).</tex>

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

Рассмотрим <tex dpi="130">s(n+1,k)</tex>::По определению, данному выше: :<tex dpi="130">(x)^{n+1}=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=Числа Стирлинга для малых N "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> }} ==Дополнительные тождества==

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

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

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

<tex>s(nСледовательно,n-1)={n \choose 2}</tex>числа Стирлинга тесно связаны друг с другом, а их связь выражается формулой:

: <tex>s(n,n-2)=\frac{1}{4} (3n-1) {n \choose 3}</texp>

<texdpi="130">\sum\limits_{k=1}^n S(n,k) s(nk,nm) (-31)^{k-m} =\left \{n \choose 2begin{array}{ll} 1, & n =m \\0, & \choose 4text{otherwise}\end{array} \right.</tex></p>

==Ссылки==* [httpGraham, Knuth, and Patashnik://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=Concrete Mathematics Second Edition 1994, ISBN 0#.D0.9F.D1.80.D0.B8.D0.BC.D0.B5.D1-201-55802-5 {{---}} 257-267 с.80 Числа Стирлинга первого рода]

* [httpВ. Липский://en.wikipediaКомбинаторика для программистов 1988, ISBN 5-03-000979-5 {{---}} 49-50 с.org/wiki/Stirling_numbers_of_the_first_kind Stirling numbers of the first kind]