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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Соотношения)
Строка 1: Строка 1:
'''Числа Стирлинга первого рода''' (''Stirling numbers of the first kind'')  —  количество [[Комбинаторные объекты|перестановок]] порядка <tex dpi="130">n</tex> с <tex dpi="130">k</tex> [[Действие перестановки на набор из элементов, представление в виде циклов|циклами]](или число способов посадить <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">n</tex> с <tex dpi="130">k</tex> циклами.  
+
'''Числа Стирлинга первого рода''' (''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>.  
  
 
==Пример==
 
==Пример==
Строка 16: Строка 16:
 
Заметим, что перестановки <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">(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">(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>
 
 
 
 
=== Рекуррентное соотношение ===
 
=== Рекуррентное соотношение ===
  
Строка 56: Строка 42:
 
:<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 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>
  
==Числа Стирлинга для малых N и K==
+
Теперь, имея рекуррентное соотношение, подсчитаем чиcла Стирлинга для малых <tex dpi="130">n</tex> и <tex dpi="130">k</tex>:
Ниже представлены некоторые значения чисел Стирлинга, которые легко подсчитать, используя рекуррентные соотношения
 
  
 
{|border="1"
 
{|border="1"
Строка 193: Строка 178:
 
| 1
 
| 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>
  
 
==Дополнительные тождества==
 
==Дополнительные тождества==
Строка 232: Строка 233:
  
 
==Ссылки==
 
==Ссылки==
* [http://ru.wikipedia.org/wiki/Числа_Стирлинга_первого_рода Числа Стирлинга первого рода]
+
* [http://ru.wikipedia.org/wiki/Числа_Стирлинга_первого_рода Википедия {{---}} Числа Стирлинга первого рода]
  
* [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind Stirling numbers of the first kind]
+
* [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind Wikipedia {{---}} Stirling numbers of the first kind]
  
 
== Литература ==
 
== Литература ==

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

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

Пример

[math]s(4,2)=11[/math]

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

[math](1)(2; 4; 3) \qquad (1)(2; 3; 4)[/math] <br\> [math](2)(1; 4; 3) \qquad (2)(1; 3; 4)[/math] <br\> [math](3)(1; 4; 2) \qquad (3)(1; 2; 4)[/math] <br\> [math](4)(1; 3; 2) \qquad (4)(1; 2; 3)[/math] <br\> [math](1; 2)(3; 4)[/math] <br\> [math](1; 4)(2; 3)[/math] <br\> [math](1; 3)(2; 4)[/math] <br\>

Заметим, что перестановки [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] 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]

Теперь, имея рекуррентное соотношение, подсчитаем чиcла Стирлинга для малых [math]n[/math] и [math]k[/math]:

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](x)^{n} = \sum_{k=0}^n s(n,k) x^k,[/math]

Следовательно, числа Стирлинга 1-го рода позволяют перейти от базиса [math](x)^{1},(x)^{2},(x)^{3} \cdots[/math] к базису [math]1,x,x^2 \cdots[/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]\left[{0\atop 0}\right]=1[/math]
[math]\left[{n\atop 0}\right]=\left[{0\atop k}\right]=0[/math], в общем случае [math]\left[{n\atop k}\right]=0[/math], если [math]k \gt n[/math]

Также

[math]\left[{n\atop 1}\right]=(n-1)![/math]
[math]\left[{n\atop n}\right]=1[/math]
[math]\left[{n\atop n-1}\right]={n \choose 2}[/math]
[math]\left[{n\atop n-2}\right]=\frac{1}{4} (3n-1) {n \choose 3}[/math]
[math]\left[{n\atop n-3}\right]={n \choose 2}{n \choose 4}[/math]

Для целых, положительных [math]l,m,n:[/math]

[math]\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! [/math]
[math]\left[{n\atop m}\right]=\sum_{k=1}^n \left[{n+1\atop k+1}\right] {k \choose m} (-1)^{m-k} [/math]
[math]\left[{m+n+1\atop m}\right]=\sum_{k=0}^n (n+k) \left[{n+k\atop k}\right][/math]

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

Если числа Стирлинга 1-го рода позволяют перейти от базиса [math](x)^{1},(x)^{2},(x)^{3} \cdots[/math] к базису [math]1,x,x^2 \cdots[/math],

то числа Стирлинга 2-го рода играют обратную роль и позволяют перейти от базиса [math]1,x,x^2 \cdots[/math] к базису [math](x)^{1},(x)^{2},(x)^{3} \cdots[/math].

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

[math]\sum_{k=1}^n S(n,k) s(k,m) (-1)^{k-m} = 1[/math], если [math]n=m[/math], иначе [math]0[/math]

См. также

Ссылки

Литература

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