Викиконспекты - Вклад участника [ru]

Числа Стирлинга первого рода

2012-12-21T15:40:23Z

83.149.2.156: /* Применение */

'''Числа Стирлинга первого рода''' (''Stirling numbers of the first kind'') — количество [[Комбинаторные объекты|перестановок]] порядка <tex dpi="130">n</tex> с <tex dpi="130">k</tex> [[Действие перестановки на набор из элементов, представление в виде циклов|циклами]]. Числа Стирлинга I рода обозначаются как <tex dpi="130">s(n,k)</tex> или <tex dpi="130">\left[{n\atop k}\right]</tex>.

==Пример==
<tex dpi="130">s(4,2)=11</tex>

Существует 11 разбиений перестановки из четырех элементов на два цикла:

<tex dpi="130">(1)(2; 4; 3) \qquad (1)(2; 3; 4)</tex> <br\>
<tex dpi="130">(2)(1; 4; 3) \qquad (2)(1; 3; 4)</tex> <br\>
<tex dpi="130">(3)(1; 4; 2) \qquad (3)(1; 2; 4)</tex> <br\>
<tex dpi="130">(4)(1; 3; 2) \qquad (4)(1; 2; 3)</tex> <br\>
<tex dpi="130">(1; 2)(3; 4)</tex> <br\>
<tex dpi="130">(1; 4)(2; 3)</tex> <br\>
<tex dpi="130">(1; 3)(2; 4)</tex> <br\>

Заметим, что перестановки <tex dpi="130">(1)(2; 3; 4)</tex> и <tex dpi="130">(1)(2; 4; 3)</tex> считаются различными, так как подмножество <tex dpi="130">(2; 3; 4)</tex> невозможно получить ни из подмножества <tex dpi="130">(1)</tex>, ни из подмножества <tex dpi="130">(2; 4; 3)</tex> с помощью циклического сдвига элементов.

==Вычисление==
=== Рекуррентное соотношение ===

Числа Стирлинга первого рода задаются рекуррентным соотношением:
:<tex dpi="130"> s(0, 0) = 1 </tex>,
:<tex dpi="130"> s(n, 0) = 0 </tex>, для <tex dpi="130">n > 0</tex>,
:<tex dpi="130"> s(0, k) = 0 </tex>, для <tex dpi="130">k > 0</tex>.

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

'''Доказательство'''

Рассмотрим <tex dpi="130">s(n+1,k)</tex>:
:По определению, данному выше:
:<tex dpi="130">(x)^{n+1}=x(x+1)(x+2)...(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> увеличатся на 1, а коэффициенты при этом не изменятся.

Так как левая и правая части равенства равны как полиномы, то равны и коэффициенты перед <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>.

{| class="wikitable"
|-
!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
|-
! 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 dpi="130">(x)^{n} = \sum_{k=0}^n s(n,k) x^k,</tex>

Следовательно, числа Стирлинга I рода позволяют перейти от базиса <tex dpi="130">(x)^{1},(x)^{2},(x)^{3}...</tex> к базису <tex dpi="130">1,x,x^2 ...</tex> (одно из основных применений)

Здесь <tex dpi="130">(x)^{n}</tex> обозначим как возрастающие факториальные степени или [http://ru.wikipedia.org/wiki/Символ_Похгаммера | символ Похгаммера]:

:<tex dpi="130">(x)^{n}=x(x+1)(x+2)...(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>

==Дополнительные тождества==

Как уже упоминалось ранее:

:<tex dpi = "160">\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 dpi="160">\left[{n\atop 1}\right]=(n-1)!</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">\left[{n\atop n-2}\right]=\frac{1}{4} (3n-1) {n \choose 3}</tex>

:<tex dpi="160">\left[{n\atop n-3}\right]={n \choose 2}{n \choose 4}</tex>

Для целых, положительных <tex>l,m,n:</tex>
:<tex dpi="160">\left[{n+1\atop m+1}\right]=\sum_{k=1}^n \left[{n\atop k}\right] {k \choose m}=n! \sum_{k=0}^n \left[{k\atop m}\right]/k! </tex>
:<tex dpi="160">\left[{n\atop m}\right]=\sum_{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_{k=0}^n (n+k) \left[{n+k\atop k}\right]</tex>

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

то числа Стирлинга 2-го рода играют обратную роль и позволяют перейти от базиса <tex dpi="130">1,x,x^2...</tex> к базису <tex dpi="130">(x)^{1},(x)^{2},(x)^{3}...</tex>

Следовательно, числа Стирлинга тесно связаны друг с другом, а их связь выражается формулой:

:<tex dpi="130">\sum_{k=1}^n S(n,k) s(k,m) (-1)^{k-m} = 1</tex>, если <tex dpi="130">n=m</tex>, иначе <tex dpi="130">0</tex>

==См. также==
* [[Числа Стирлинга второго рода]]

==Ссылки==
* [http://ru.wikipedia.org/wiki/Числа_Стирлинга_первого_рода Википедия {{---}} Числа Стирлинга первого рода]

* [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind Wikipedia {{---}} Stirling numbers of the first kind]

== Литература ==
* Graham, Knuth, and Patashnik: Concrete Mathematics Second Edition 1994 ISBN 0-201-55802-5
* В. Липский: Комбинаторика для программистов 1988 ISBN 5-03-000979-5

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Числа Стирлинга первого рода

2012-12-21T15:39:47Z

83.149.2.156: /* Связь между числами Стирлинга */

'''Числа Стирлинга первого рода''' (''Stirling numbers of the first kind'') — количество [[Комбинаторные объекты|перестановок]] порядка <tex dpi="130">n</tex> с <tex dpi="130">k</tex> [[Действие перестановки на набор из элементов, представление в виде циклов|циклами]]. Числа Стирлинга I рода обозначаются как <tex dpi="130">s(n,k)</tex> или <tex dpi="130">\left[{n\atop k}\right]</tex>.

==Пример==
<tex dpi="130">s(4,2)=11</tex>

Существует 11 разбиений перестановки из четырех элементов на два цикла:

<tex dpi="130">(1)(2; 4; 3) \qquad (1)(2; 3; 4)</tex> <br\>
<tex dpi="130">(2)(1; 4; 3) \qquad (2)(1; 3; 4)</tex> <br\>
<tex dpi="130">(3)(1; 4; 2) \qquad (3)(1; 2; 4)</tex> <br\>
<tex dpi="130">(4)(1; 3; 2) \qquad (4)(1; 2; 3)</tex> <br\>
<tex dpi="130">(1; 2)(3; 4)</tex> <br\>
<tex dpi="130">(1; 4)(2; 3)</tex> <br\>
<tex dpi="130">(1; 3)(2; 4)</tex> <br\>

Заметим, что перестановки <tex dpi="130">(1)(2; 3; 4)</tex> и <tex dpi="130">(1)(2; 4; 3)</tex> считаются различными, так как подмножество <tex dpi="130">(2; 3; 4)</tex> невозможно получить ни из подмножества <tex dpi="130">(1)</tex>, ни из подмножества <tex dpi="130">(2; 4; 3)</tex> с помощью циклического сдвига элементов.

==Вычисление==
=== Рекуррентное соотношение ===

Числа Стирлинга первого рода задаются рекуррентным соотношением:
:<tex dpi="130"> s(0, 0) = 1 </tex>,
:<tex dpi="130"> s(n, 0) = 0 </tex>, для <tex dpi="130">n > 0</tex>,
:<tex dpi="130"> s(0, k) = 0 </tex>, для <tex dpi="130">k > 0</tex>.

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

'''Доказательство'''

Рассмотрим <tex dpi="130">s(n+1,k)</tex>:
:По определению, данному выше:
:<tex dpi="130">(x)^{n+1}=x(x+1)(x+2)...(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> увеличатся на 1, а коэффициенты при этом не изменятся.

Так как левая и правая части равенства равны как полиномы, то равны и коэффициенты перед <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>.

{| class="wikitable"
|-
!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
|-
! 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 dpi="130">(x)^{n} = \sum_{k=0}^n s(n,k) x^k,</tex>

Следовательно, числа Стирлинга I рода позволяют перейти от базиса <tex dpi="130">(x)^{1},(x)^{2},(x)^{3}...</tex> к базису <tex dpi="130">1,x,x^2 ...</tex> (одно из основных применений)

Здесь <tex dpi="130">(x)^{n}</tex> обозначим как возрастающие факториальные степени или [http://ru.wikipedia.org/wiki/Символ_Похгаммера| символ Похгаммера]:

:<tex dpi="130">(x)^{n}=x(x+1)(x+2)...(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>

==Дополнительные тождества==

Как уже упоминалось ранее:

:<tex dpi = "160">\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 dpi="160">\left[{n\atop 1}\right]=(n-1)!</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">\left[{n\atop n-2}\right]=\frac{1}{4} (3n-1) {n \choose 3}</tex>

:<tex dpi="160">\left[{n\atop n-3}\right]={n \choose 2}{n \choose 4}</tex>

Для целых, положительных <tex>l,m,n:</tex>
:<tex dpi="160">\left[{n+1\atop m+1}\right]=\sum_{k=1}^n \left[{n\atop k}\right] {k \choose m}=n! \sum_{k=0}^n \left[{k\atop m}\right]/k! </tex>
:<tex dpi="160">\left[{n\atop m}\right]=\sum_{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_{k=0}^n (n+k) \left[{n+k\atop k}\right]</tex>

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

то числа Стирлинга 2-го рода играют обратную роль и позволяют перейти от базиса <tex dpi="130">1,x,x^2...</tex> к базису <tex dpi="130">(x)^{1},(x)^{2},(x)^{3}...</tex>

Следовательно, числа Стирлинга тесно связаны друг с другом, а их связь выражается формулой:

:<tex dpi="130">\sum_{k=1}^n S(n,k) s(k,m) (-1)^{k-m} = 1</tex>, если <tex dpi="130">n=m</tex>, иначе <tex dpi="130">0</tex>

==См. также==
* [[Числа Стирлинга второго рода]]

==Ссылки==
* [http://ru.wikipedia.org/wiki/Числа_Стирлинга_первого_рода Википедия {{---}} Числа Стирлинга первого рода]

* [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind Wikipedia {{---}} Stirling numbers of the first kind]

== Литература ==
* Graham, Knuth, and Patashnik: Concrete Mathematics Second Edition 1994 ISBN 0-201-55802-5
* В. Липский: Комбинаторика для программистов 1988 ISBN 5-03-000979-5

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Числа Стирлинга первого рода

2012-12-21T15:35:21Z

83.149.2.156:

'''Числа Стирлинга первого рода''' (''Stirling numbers of the first kind'') — количество [[Комбинаторные объекты|перестановок]] порядка <tex dpi="130">n</tex> с <tex dpi="130">k</tex> [[Действие перестановки на набор из элементов, представление в виде циклов|циклами]]. Числа Стирлинга I рода обозначаются как <tex dpi="130">s(n,k)</tex> или <tex dpi="130">\left[{n\atop k}\right]</tex>.

==Пример==
<tex dpi="130">s(4,2)=11</tex>

Существует 11 разбиений перестановки из четырех элементов на два цикла:

<tex dpi="130">(1)(2; 4; 3) \qquad (1)(2; 3; 4)</tex> <br\>
<tex dpi="130">(2)(1; 4; 3) \qquad (2)(1; 3; 4)</tex> <br\>
<tex dpi="130">(3)(1; 4; 2) \qquad (3)(1; 2; 4)</tex> <br\>
<tex dpi="130">(4)(1; 3; 2) \qquad (4)(1; 2; 3)</tex> <br\>
<tex dpi="130">(1; 2)(3; 4)</tex> <br\>
<tex dpi="130">(1; 4)(2; 3)</tex> <br\>
<tex dpi="130">(1; 3)(2; 4)</tex> <br\>

Заметим, что перестановки <tex dpi="130">(1)(2; 3; 4)</tex> и <tex dpi="130">(1)(2; 4; 3)</tex> считаются различными, так как подмножество <tex dpi="130">(2; 3; 4)</tex> невозможно получить ни из подмножества <tex dpi="130">(1)</tex>, ни из подмножества <tex dpi="130">(2; 4; 3)</tex> с помощью циклического сдвига элементов.

==Вычисление==
=== Рекуррентное соотношение ===

Числа Стирлинга первого рода задаются рекуррентным соотношением:
:<tex dpi="130"> s(0, 0) = 1 </tex>,
:<tex dpi="130"> s(n, 0) = 0 </tex>, для <tex dpi="130">n > 0</tex>,
:<tex dpi="130"> s(0, k) = 0 </tex>, для <tex dpi="130">k > 0</tex>.

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

'''Доказательство'''

Рассмотрим <tex dpi="130">s(n+1,k)</tex>:
:По определению, данному выше:
:<tex dpi="130">(x)^{n+1}=x(x+1)(x+2)...(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> увеличатся на 1, а коэффициенты при этом не изменятся.

Так как левая и правая части равенства равны как полиномы, то равны и коэффициенты перед <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>.

{| class="wikitable"
|-
!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
|-
! 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 dpi="130">(x)^{n} = \sum_{k=0}^n s(n,k) x^k,</tex>

Следовательно, числа Стирлинга I рода позволяют перейти от базиса <tex dpi="130">(x)^{1},(x)^{2},(x)^{3}...</tex> к базису <tex dpi="130">1,x,x^2 ...</tex> (одно из основных применений)

Здесь <tex dpi="130">(x)^{n}</tex> обозначим как возрастающие факториальные степени или [http://ru.wikipedia.org/wiki/Символ_Похгаммера| символ Похгаммера]:

:<tex dpi="130">(x)^{n}=x(x+1)(x+2)...(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>

==Дополнительные тождества==

Как уже упоминалось ранее:

:<tex dpi = "160">\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 dpi="160">\left[{n\atop 1}\right]=(n-1)!</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">\left[{n\atop n-2}\right]=\frac{1}{4} (3n-1) {n \choose 3}</tex>

:<tex dpi="160">\left[{n\atop n-3}\right]={n \choose 2}{n \choose 4}</tex>

Для целых, положительных <tex>l,m,n:</tex>
:<tex dpi="160">\left[{n+1\atop m+1}\right]=\sum_{k=1}^n \left[{n\atop k}\right] {k \choose m}=n! \sum_{k=0}^n \left[{k\atop m}\right]/k! </tex>
:<tex dpi="160">\left[{n\atop m}\right]=\sum_{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_{k=0}^n (n+k) \left[{n+k\atop k}\right]</tex>

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

то числа Стирлинга 2-го рода играют обратную роль и позволяют перейти от базиса <tex dpi="130">1,x,x^2...</tex> к базису <tex dpi="130">(x)^{1},(x)^{2},(x)^{3}...</tex>.

Следовательно, числа Стирлинга тесно связаны друг с другом, а их связь выражается формулой:

:<tex dpi="130">\sum_{k=1}^n S(n,k) s(k,m) (-1)^{k-m} = 1</tex>, если <tex dpi="130">n=m</tex>, иначе <tex dpi="130">0</tex>

==См. также==
* [[Числа Стирлинга второго рода]]

==Ссылки==
* [http://ru.wikipedia.org/wiki/Числа_Стирлинга_первого_рода Википедия {{---}} Числа Стирлинга первого рода]

* [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind Wikipedia {{---}} Stirling numbers of the first kind]

== Литература ==
* Graham, Knuth, and Patashnik: Concrete Mathematics Second Edition 1994 ISBN 0-201-55802-5
* В. Липский: Комбинаторика для программистов 1988 ISBN 5-03-000979-5

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Числа Стирлинга первого рода

2012-12-21T15:14:52Z

83.149.2.156:

'''Числа Стирлинга первого рода''' (''Stirling numbers of the first kind'') — количество [[Комбинаторные объекты|перестановок]] порядка <tex dpi="130">n</tex> с <tex dpi="130">k</tex> [[Действие перестановки на набор из элементов, представление в виде циклов|циклами]]. Числа Стирлинга 1-го рода обозначаются как <tex dpi="130">s(n,k)</tex> или <tex dpi="130">\left[{n\atop k}\right]</tex>.

==Пример==
<tex dpi="130">s(4,2)=11</tex>

Существует 11 разбиений перестановки из четырех элементов на два цикла:

<tex dpi="130">(1)(2; 4; 3) \qquad (1)(2; 3; 4)</tex> <br\>
<tex dpi="130">(2)(1; 4; 3) \qquad (2)(1; 3; 4)</tex> <br\>
<tex dpi="130">(3)(1; 4; 2) \qquad (3)(1; 2; 4)</tex> <br\>
<tex dpi="130">(4)(1; 3; 2) \qquad (4)(1; 2; 3)</tex> <br\>
<tex dpi="130">(1; 2)(3; 4)</tex> <br\>
<tex dpi="130">(1; 4)(2; 3)</tex> <br\>
<tex dpi="130">(1; 3)(2; 4)</tex> <br\>

Заметим, что перестановки <tex dpi="130">(1)(2; 3; 4)</tex> и <tex dpi="130">(1)(2; 4; 3)</tex> считаются различными, так как подмножество <tex dpi="130">(2; 3; 4)</tex> невозможно получить ни из подмножества <tex dpi="130">(1)</tex>, ни из подмножества <tex dpi="130">(2; 4; 3)</tex> с помощью циклического сдвига элементов.

==Вычисления==
=== Рекуррентное соотношение ===

Числа Стирлинга первого рода задаются рекуррентным соотношением:
:<tex dpi="130"> s(0, 0) = 1 </tex>,
:<tex dpi="130"> s(n, 0) = 0 </tex>, для <tex dpi="130">n > 0</tex>,
:<tex dpi="130"> s(0, k) = 0 </tex>, для <tex dpi="130">k > 0</tex>.

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

'''Доказательство'''

Рассмотрим <tex dpi="130">s(n+1,k)</tex>:
:По определению, данному выше:
:<tex dpi="130">(x)^{n+1}=x(x+1)(x+2)\cdots(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> увеличатся на 1, а коэффициенты при этом не изменятся.

Так как левая и правая части равенства равны как полиномы, то равны и коэффициенты перед <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>

Теперь, имея рекуррентное соотношение, подсчитаем чиcла Стирлинга для малых <tex dpi="130">n</tex> и <tex dpi="130">k</tex>:

{|border="1"
|-
| 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 dpi="130">(x)^{n} = \sum_{k=0}^n s(n,k) x^k,</tex>

Следовательно, числа Стирлинга 1-го рода позволяют перейти от базиса <tex dpi="130">(x)^{1},(x)^{2},(x)^{3} \cdots</tex> к базису <tex dpi="130">1,x,x^2 \cdots</tex> (одно из основных применений)

Здесь <tex dpi="130">(x)^{n}</tex> обозначим как возрастающие факториальные степени или символ Похгаммера:

:<tex dpi="130">(x)^{n}=x(x+1)(x+2)\cdots(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>

==Дополнительные тождества==

Как уже упоминалось ранее:

:<tex dpi = "160">\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 dpi="160">\left[{n\atop 1}\right]=(n-1)!</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">\left[{n\atop n-2}\right]=\frac{1}{4} (3n-1) {n \choose 3}</tex>

:<tex dpi="160">\left[{n\atop n-3}\right]={n \choose 2}{n \choose 4}</tex>

Для целых, положительных <tex>l,m,n:</tex>
:<tex dpi="160">\left[{n+1\atop m+1}\right]=\sum_{k=1}^n \left[{n\atop k}\right] {k \choose m}=n! \sum_{k=0}^n \left[{k\atop m}\right]/k! </tex>
:<tex dpi="160">\left[{n\atop m}\right]=\sum_{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_{k=0}^n (n+k) \left[{n+k\atop k}\right]</tex>

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

то числа Стирлинга 2-го рода играют обратную роль и позволяют перейти от базиса <tex dpi="130">1,x,x^2 \cdots</tex> к базису <tex dpi="130">(x)^{1},(x)^{2},(x)^{3} \cdots</tex>.

Следовательно, числа Стирлинга тесно связаны друг с другом, а их связь выражается формулой:

:<tex dpi="130">\sum_{k=1}^n S(n,k) s(k,m) (-1)^{k-m} = 1</tex>, если <tex dpi="130">n=m</tex>, иначе <tex dpi="130">0</tex>

==См. также==
* [[Числа Стирлинга второго рода]]

==Ссылки==
* [http://ru.wikipedia.org/wiki/Числа_Стирлинга_первого_рода Википедия {{---}} Числа Стирлинга первого рода]

* [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind Wikipedia {{---}} Stirling numbers of the first kind]

== Литература ==
* Graham, Knuth, and Patashnik: Concrete Mathematics Second Edition 1994 ISBN 0-201-55802-5
* В. Липский: Комбинаторика для программистов 1988 ISBN 5-03-000979-5

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]