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

2012-12-18T16:53:20Z

83.149.2.133:

'''Числа Стирлинга первого рода''' (''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(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]</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>

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

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

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

==Числа Стирлинга для малых N и K==
Ниже представлены некоторые значения чисел Стирлинга, которые легко подсчитать, используя рекуррентные соотношения

{| class="wikitable"
|-
! 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>s(0,0)=1</tex>

<tex>s(n,0)=s(0,k)=0</tex>, в общем случае <tex>s(n,k)=0</tex>, если <tex>k > n</tex>

Также

<tex>s(n,1)=(n-1)!</tex>

<tex>s(n,n)=1</tex>

<tex>s(n,n-1)={n \choose 2}</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}</tex>

<tex>\sum_{k=0}^n s(n,k) = n!</tex> — конечная сумма.

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

==Ссылки==
* [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.80 Числа Стирлинга первого рода]

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

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

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

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