Изменения

'''Числа Стирлинга первого рода''' (англ. ''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">(3)(1; 4; 2) \qquad (3)(1; 2; 4)</tex>n <tex dpi="130">(4)(1; 3; 2) \qquad (4)(1; 2; 3)</tex>::<texdpi="130">(x1; 2)^{(3}; 4)</tex> <tex dpi=x"130">(x+1; 4)(x+2; 3)</tex> <tex dpi="130">(1 \cdot x^; 3 + 3 \cdot x^)(2 + 2 \cdot x; 4)</tex> Заметим, здесь коэффициенты при что разбиения <texdpi="130">x^k(1)(2; 3; 4)</tex> — это и <texdpi="130">s(1)(2; 4; 3,k)</tex>считаются различными, то есть::так как цикл <texdpi="130">s(2; 3,3; 4)=1</tex> :невозможно получить ни из подмножества <texdpi="130">s(3,21)=3</tex> :, ни из подмножества <texdpi="130">s(2; 4; 3,1)=2</tex> с помощью циклического сдвига элементов.

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

Рассмотрим <texdpi="130">s(n+1,k)</tex>:

:<texdpi="130">(x)^{n+1}=x(x+1)(x+2)\cdotsdots (x+n-1)(x+n) = n(x)^{n}+x(x)^{n}</tex>

Заметим, что коэффициенты <texdpi="130">(x)^{n+1}</tex> — это <texdpi="130">s(n+1,k)</tex>

Аналогично можно сказать, что коэффициенты <texdpi="130">n(x)^{n}</tex> — это <texdpi="130">ns(n,k)</tex>

А коэффициенты <texdpi="130">x(x)^{n}</tex> — это <texdpi="130">s(n,k-1)</tex>, так как степени при <texdpi="130">x</tex> увеличатся на <tex> 1</tex>, а коэффициенты при этом не изменятся.

Так как левая и правая части равенства равны как полиномы, то равны и коэффициенты перед <texdpi="130">x^k</tex>, следовательно справедливо равенство::<texdpi="130">s(n+1,k)=ns(n,k)+s(n,k-1)</tex> или <texdpi="130">s(n,k)=(n-1)s(n-1,k)+ s(n-1,k-1)</tex>

==Числа Стирлинга для малых N и K= Таблица значений ===Ниже представлены некоторые Найдём числовые значения чисел Стирлинга<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>

Для целых, положительных <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>#:Второе равенство доказывается путем постепенного спуска вниз: #:<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>#:Чтобы доказать первое, будем использовать биекцию(из прошлого раздела) в факториальные степени, а также формулу <texdpi="160">s(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(nx)^{1},n(x)^{2},(x)^{3} \dots </tex> к базису <tex dpi="130">1,x,x^2 \dots </tex>,

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

<texdpi="130">\sum_sum\limits_{k=01}^n sS(n,k) s(k,m) (-1)^{k-m} = \left \{\begin{array}{ll} 1, & n!=m \\0, & \text{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]