Числа Стирлинга первого рода — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Создал статью, добавил шаблон "в разработке")
 
Строка 1: Строка 1:
−
{{В разработке}}
+
{{Определение
 +
|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 перестановок] порядка <tex>n</tex> с <tex>k</tex> циклами.}}
 +
 
 +
==Соотношения==
 +
Числами Стирлинга первого рода (со знаком) <tex>s(n, k)</tex> называются коэффициенты многочлена:
 +
<math>(x)_{n} = \sum_{k=0}^n s(n,k) x^k,</math>
 +
 
 +
где <math>(x)_n</math> — [http://en.wikipedia.org/wiki/Pochhammer_symbol символ Похгаммера] (убывающий факториал):
 +
: <math>(x)_{n}=x(x-1)(x-2)\cdots(x-n+1).</math>
 +
 
 +
Числа имеют чередующийся знак, а их абсолютные значения, называемые числами Стирлинга первого рода (без знака), задают количество перестановок множества, состоящего из <tex>n</tex> элементов с <tex>k</tex> циклами.
 +
Беззнаковые числа Стирлинга задаются коэффициентами многочлена: <math>(x)^{n} = \sum_{k=0}^n s(n,k) x^k,</math>
 +
 
 +
где <math>(x)^n</math> — символ Похгаммера (возрастающий факториал):
 +
: <math>(x)^{n}=x(x+1)(x+2)\cdots(x+n-1).</math>
 +
 
 +
=== Рекуррентное соотношение ===
 +
 
 +
Числа Стирлинга первого рода задаются рекуррентным соотношением:
 +
:<math> s(0, 0) = 1 </math>,
 +
:<math> s(n, 0) = 0 </math>, для <tex>n > 0</tex>,
 +
:<math> s(0, k) = 0 </math>, для <tex>k > 0</tex>,
 +
:для чисел со знаком: <math> s(n, k) = s(n-1, k-1) - (n-1) \cdot s(n-1, k) </math> для <math>0 < k < n.</math>
 +
:для чисел без знака: <math> s(n, k) = s(n-1, k-1) + (n-1) \cdot s(n-1, k) </math> для <math>0 < k < n.</math>
 +
 
 +
==Числа Стирлинга для малых 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>s(n,2)=(n-1)! H_{n-1}</tex>, где <tex>H_{n}</tex> — гармоническое число([http://en.wikipedia.org/wiki/Harmonic_number Harmonic number])
 +
 
 +
<tex>s(n,3)=\frac{1}{2} (n-1)! \left[ (H_{n-1})^2 - H_{n-1}^{(2)} \right]</tex>, где <tex>H_{n}^{(2)}</tex> — обобщенное гармоническое число([http://en.wikipedia.org/wiki/Harmonic_number#Generalized_harmonic_numbers Generalized harmonic number])
 +
 
 +
<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]

Версия 22:57, 17 декабря 2012

Определение:
Числа Стирлинга первого рода (Stirling numbers of the first kind) — количество перестановок порядка [math]n[/math] с [math]k[/math] циклами.


Соотношения

Числами Стирлинга первого рода (со знаком) [math]s(n, k)[/math] называются коэффициенты многочлена: [math](x)_{n} = \sum_{k=0}^n s(n,k) x^k,[/math]

где [math](x)_n[/math] — символ Похгаммера (убывающий факториал):

[math](x)_{n}=x(x-1)(x-2)\cdots(x-n+1).[/math]

Числа имеют чередующийся знак, а их абсолютные значения, называемые числами Стирлинга первого рода (без знака), задают количество перестановок множества, состоящего из [math]n[/math] элементов с [math]k[/math] циклами. Беззнаковые числа Стирлинга задаются коэффициентами многочлена: [math](x)^{n} = \sum_{k=0}^n s(n,k) x^k,[/math]

где [math](x)^n[/math] — символ Похгаммера (возрастающий факториал):

[math](x)^{n}=x(x+1)(x+2)\cdots(x+n-1).[/math]

Рекуррентное соотношение

Числа Стирлинга первого рода задаются рекуррентным соотношением:

[math] s(0, 0) = 1 [/math],
[math] s(n, 0) = 0 [/math], для [math]n \gt 0[/math],
[math] s(0, k) = 0 [/math], для [math]k \gt 0[/math],
для чисел со знаком: [math] s(n, k) = s(n-1, k-1) - (n-1) \cdot s(n-1, k) [/math] для [math]0 \lt k \lt n.[/math]
для чисел без знака: [math] s(n, k) = s(n-1, k-1) + (n-1) \cdot s(n-1, k) [/math] для [math]0 \lt k \lt n.[/math]

Числа Стирлинга для малых N и K

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

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

Тождества, включающие числа Стирлинга первого рода

Простые тождества

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

[math]s(0,0)=1[/math]

[math]s(n,0)=s(0,k)=0[/math], в общем случае [math]s(n,k)=0[/math], если [math]k \gt n[/math]

Также

[math]s(n,1)=(n-1)![/math]

[math]s(n,n)=1[/math]

[math]s(n,n-1)={n \choose 2}[/math]

[math]s(n,n-2)=\frac{1}{4} (3n-1) {n \choose 3}[/math]

[math]s(n,n-3)={n \choose 2}{n \choose 4}[/math]

Другие тождества

[math]s(n,2)=(n-1)! H_{n-1}[/math], где [math]H_{n}[/math] — гармоническое число(Harmonic number)

[math]s(n,3)=\frac{1}{2} (n-1)! \left[ (H_{n-1})^2 - H_{n-1}^{(2)} \right][/math], где [math]H_{n}^{(2)}[/math] — обобщенное гармоническое число(Generalized harmonic number)

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

См. также

Ссылки

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Числа_Стирлинга_первого_рода&oldid=27886»