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

Определение:

Числа Стирлинга первого рода (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] — конечная сумма.

См. также

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

Ссылки

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

• Stirling numbers of the first kind