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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 35: Строка 35:
 
:<tex>(x)^{n+1}=x(x+1)(x+2)\cdots(x+n-1)(x+n) = n(x)^{n}+x(x)^{n}</tex>
 
:<tex>(x)^{n+1}=x(x+1)(x+2)\cdots(x+n-1)(x+n) = n(x)^{n}+x(x)^{n}</tex>
  
Заметим, что коэффициенты <tex>(x)^{n+1}</tex> — это <tex>s(n,k)</tex>
+
Заметим, что коэффициенты <tex>(x)^{n+1}</tex> — это <tex>s(n+1,k)</tex>
  
 
Аналогично можно сказать, что коэффициенты <tex>n(x)^{n}</tex> — это <tex>ns(n,k)</tex>
 
Аналогично можно сказать, что коэффициенты <tex>n(x)^{n}</tex> — это <tex>ns(n,k)</tex>

Версия 21:16, 18 декабря 2012

Числа Стирлинга первого рода (Stirling numbers of the first kind) — количество перестановок порядка [math]n[/math] с [math]k[/math] циклами. Иначе говоря, число Стирлинга первого рода определяется как количество перестановок из [math]n[/math] элементов на [math]k[/math] не пустых подмножеств, при этом две перестановки считаются различными, если хотя бы одно подмножество из первой перестановки нельзя получить ни из одного подмножества второй перестановки с помощью циклического сдвига. Числа Стирлинга 1-го рода обозначаются как [math]s(n,k)[/math] или [math]\left[{n\atop k}\right][/math].

Пример

[math]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])[/math].

Заметим, что перестановки [math][1][2;3;4][/math] и [math][1][2;4;3][/math] считаются различными, так как подмножество [math][2;3;4][/math] невозможно получить ни из подмножества [math][1][/math], ни из подмножества [math][2;4;3][/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=3[/math]:

[math](x)^{3}=x(x+1)(x+2)=1 \cdot x^3 + 3 \cdot x^2 + 2 \cdot x[/math], здесь коэффициенты при [math]x^k[/math] — это [math]s(3,k)[/math], то есть:
[math]s(3,3)=1[/math]
[math]s(3,2)=3[/math]
[math]s(3,1)=2[/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]n[/math] элементов в виде [math]k[/math] циклов либо помещает последний элемент([math]n-[/math]ый) в отдельный цикл [math]s(n-1, k-1)[/math] способами, либо вставляет этот элемент в одно из [math]s(n-1, k)[/math] циклических представлений первых [math](n-1)[/math] элементов. В последнем случае существует [math](n-1)[/math] различных способов подобной вставки. Например, при вставке элемента [math]4[/math] в цикл [math][1;2;3][/math] можно получить только 3 разных цикла: [math][1;2;3;4], [1;2;4;3], [1;4;2;3][/math]. Таким образом, рекуррентность имеет вид:

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

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

Рассмотрим [math]s(n+1,k)[/math]:

По определению, данному выше:
[math](x)^{n+1}=x(x+1)(x+2)\cdots(x+n-1)(x+n) = n(x)^{n}+x(x)^{n}[/math]

Заметим, что коэффициенты [math](x)^{n+1}[/math] — это [math]s(n+1,k)[/math]

Аналогично можно сказать, что коэффициенты [math]n(x)^{n}[/math] — это [math]ns(n,k)[/math]

А коэффициенты [math]x(x)^{n}[/math] — это [math]s(n,k-1)[/math], так как степени при [math]x[/math] увеличатся на 1, а коэффициенты при этом не изменятся.

Так как левая и правая части равенства равны как полиномы, то равны и коэффициенты перед [math]x^k[/math], следовательно справедливо равенство:

[math]s(n+1,k)=ns(n,k)+s(n,k-1)[/math] или [math]s(n,k)=(n-1)s(n-1,k)+ s(n-1,k-1)[/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]\sum_{k=0}^n s(n,k) = n![/math] — конечная сумма.


См. также

Ссылки