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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример)
м (rollbackEdits.php mass rollback)
 
(не показаны 24 промежуточные версии 9 участников)
Строка 1: Строка 1:
'''Числа Стирлинга первого рода''' (''Stirling numbers of the first kind'')  —  количество [[Комбинаторные объекты|перестановок]] порядка <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>n</tex> с <tex>k</tex> циклами.  
+
'''Числа Стирлинга первого рода''' (англ. ''Stirling numbers of the first kind'')  —  количество [[Комбинаторные объекты|перестановок]] порядка <tex dpi="130">n</tex> с <tex dpi="130">k</tex> [[Действие перестановки на набор из элементов, представление в виде циклов|циклами]]. Числа Стирлинга I рода обозначаются как <tex dpi="130">s(n,k)</tex> или <tex dpi="170">\left[{n\atop k}\right]</tex>.  
  
 
==Пример==
 
==Пример==
<tex>s(4,2)=11</tex>
+
<tex dpi="130">s(4,2)=11</tex>
  
Существует 11 разбиений перестановки из четырех элементов на два цикла:
+
Существует <tex> 11 </tex> разбиений перестановки из четырех элементов на два цикла:
  
<tex>(1)(2; 4; 3) \qquad (1)(2; 3; 4)</tex> <br\>
+
<tex dpi="130">(1)(2; 4; 3) \qquad (1)(2; 3; 4)</tex>
<tex>(2)(1; 4; 3) \qquad (2)(1; 3; 4)</tex> <br\>
 
<tex>(3)(1; 4; 2) \qquad (3)(1; 2; 4)</tex> <br\>
 
<tex>(4)(1; 3; 2) \qquad (4)(1; 2; 3)</tex> <br\>
 
<tex>(1; 2)(3; 4)</tex> <br\>
 
<tex>(1; 4)(2; 3)</tex> <br\>
 
<tex>(1; 3)(2; 4)</tex> <br\>
 
  
Заметим, что перестановки <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 dpi="130">(2)(1; 4; 3) \qquad (2)(1; 3; 4)</tex>
  
==Соотношения==
+
<tex dpi="130">(3)(1; 4; 2) \qquad (3)(1; 2; 4)</tex>  
Равносильное определение получается, если числа Стирлинга задать как коэффициенты в разложении: <tex>(x)^{n} = \sum_{k=0}^n s(n,k) x^k,</tex>
 
  
Следовательно, числа Стирлинга 1-го рода позволяют перейти от базиса <tex>(x)^{1},(x)^{2},(x)^{3} \cdots</tex> к базису <tex>1,x,x^2 \cdots</tex>
+
<tex dpi="130">(4)(1; 3; 2) \qquad (4)(1; 2; 3)</tex>
  
Здесь <tex>(x)^{n}</tex> обозначим как возрастающие факториальные степени:
+
<tex dpi="130">(1; 2)(3; 4)</tex>
  
:<tex>(x)^{n}=x(x+1)(x+2)\cdots(x+n-1).</tex>
+
<tex dpi="130">(1; 4)(2; 3)</tex>
  
Для ясности рассмотрим пример, при котором <tex>n=3</tex>:
+
<tex dpi="130">(1; 3)(2; 4)</tex>
:<tex>(x)^{3}=x(x+1)(x+2)=1 \cdot x^3 + 3 \cdot x^2 + 2 \cdot x</tex>, здесь коэффициенты при <tex>x^k</tex> — это <tex>s(3,k)</tex>, то есть:
+
 
:<tex>s(3,3)=1</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>s(3,2)=3</tex>  
 
:<tex>s(3,1)=2</tex>  
 
  
 +
==Вычисление==
 
=== Рекуррентное соотношение ===
 
=== Рекуррентное соотношение ===
  
Числа Стирлинга первого рода задаются рекуррентным соотношением:
+
Выведем рекуррентную формулу для вычисления чисел Стирлинга первого рода. Каждое представление <tex dpi="130">n</tex> элементов в виде <tex dpi="130">k</tex> циклов либо помещает последний элемент (<tex dpi="130">n-</tex>ый) в отдельный цикл <tex dpi="130">s(n-1, k-1)</tex> способами, либо вставляет этот элемент в одно из <tex dpi="130">s(n-1, k)</tex> циклических представлений первых <tex dpi="130">(n-1)</tex> элементов. В последнем случае существует <tex dpi="130">(n-1)</tex> различных способов подобной вставки. Например, при вставке элемента <tex>4</tex> в цикл <tex>(1;2;3)</tex> можно получить только <tex> 3 </tex> разных цикла: <tex dpi="130">(1;2;3;4), (1;2;4;3), (1;4;2;3)</tex>. Таким образом, рекуррентность имеет вид:
:<tex> s(0, 0) = 1 </tex>,
+
<p>
:<tex> s(n, 0) = 0 </tex>, для <tex>n > 0</tex>,
+
<tex dpi="130">
:<tex> s(0, k) = 0 </tex>, для <tex>k > 0</tex>.
+
s(n, k) =
 
+
\left \{\begin{array}{ll} s(0, 0) = 1, \\
Выведем рекуррентную формулу для вычисления чисел Стирлинга первого рода. Каждое представление <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>. Таким образом, рекуррентность имеет вид:
+
s(n, 0) = 0, & n > 0  \\
:<tex>s(n,k)=s(n-1,k-1)+(n-1)s(n-1,k)</tex>
+
s(0, k) = 0, & k > 0 \\
 +
s(n,k) = s(n-1,k-1)+(n-1)s(n-1,k), & n,k > 0 \end{array} \right.
 +
</tex>
 +
</p>
  
 
'''Доказательство'''
 
'''Доказательство'''
  
Рассмотрим <tex>s(n+1,k)</tex>:
+
Рассмотрим <tex dpi="130">s(n+1,k)</tex>:
 
:По определению, данному выше:  
 
:По определению, данному выше:  
:<tex>(x)^{n+1}=x(x+1)(x+2)\cdots(x+n-1)(x+n) = n(x)^{n}+x(x)^{n}</tex>
+
:<tex dpi="130">(x)^{n+1}=x(x+1)(x+2) \dots (x+n-1)(x+n) = n(x)^{n}+x(x)^{n}</tex>
  
Заметим, что коэффициенты <tex>(x)^{n+1}</tex> — это <tex>s(n+1,k)</tex>
+
Заметим, что коэффициенты <tex dpi="130">(x)^{n+1}</tex> — это <tex dpi="130">s(n+1,k)</tex>
  
Аналогично можно сказать, что коэффициенты <tex>n(x)^{n}</tex> — это <tex>ns(n,k)</tex>
+
Аналогично можно сказать, что коэффициенты <tex dpi="130">n(x)^{n}</tex> — это <tex dpi="130">ns(n,k)</tex>
  
А коэффициенты <tex>x(x)^{n}</tex> — это <tex>s(n,k-1)</tex>, так как степени при <tex>x</tex> увеличатся на 1, а коэффициенты при этом не изменятся.
+
А коэффициенты <tex dpi="130">x(x)^{n}</tex> — это <tex dpi="130">s(n,k-1)</tex>, так как степени при <tex dpi="130">x</tex> увеличатся на <tex> 1 </tex>, а коэффициенты при этом не изменятся.
  
Так как левая и правая части равенства равны как полиномы, то равны и коэффициенты перед <tex>x^k</tex>, следовательно справедливо равенство:
+
Так как левая и правая части равенства равны как полиномы, то равны и коэффициенты перед <tex dpi="130">x^k</tex>, следовательно справедливо равенство:
:<tex>s(n+1,k)=ns(n,k)+s(n,k-1)</tex> или <tex>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==
+
=== Таблица значений ===
Ниже представлены некоторые значения чисел Стирлинга, которые легко подсчитать, используя рекуррентные соотношения
+
Найдём числовые значения <tex>s(n, k)</tex> для малых <tex>n</tex> и <tex>k</tex>.
  
{|border="1"
+
{| class="wikitable"
 
|-
 
|-
| n\k
+
!width="20"| n\k
| 0
+
!width="40"| 0
| 1
+
!width="40"| 1
| 2
+
!width="40"| 2
| 3
+
!width="40"| 3
| 4
+
!width="40"| 4
| 5
+
!width="40"| 5
| 6
+
!width="40"| 6
| 7
+
!width="40"| 7
| 8
+
!width="40"| 8
| 9
+
!width="40"| 9
 
|-
 
|-
| 0
+
! 0
 
| 1
 
| 1
 
|
 
|
Строка 85: Строка 80:
 
|
 
|
 
|-
 
|-
| 1
+
! 1
 
| 0
 
| 0
 
| 1
 
| 1
Строка 97: Строка 92:
 
|
 
|
 
|-
 
|-
| 2
+
! 2
 
| 0
 
| 0
 
| 1
 
| 1
Строка 109: Строка 104:
 
|
 
|
 
|-
 
|-
| 3
+
! 3
 
| 0
 
| 0
 
| 2
 
| 2
Строка 121: Строка 116:
 
|
 
|
 
|-
 
|-
| 4
+
! 4
 
| 0
 
| 0
 
| 6
 
| 6
Строка 133: Строка 128:
 
|
 
|
 
|-
 
|-
| 5
+
! 5
 
| 0
 
| 0
 
| 24
 
| 24
Строка 145: Строка 140:
 
|
 
|
 
|-
 
|-
| 6
+
! 6
 
| 0
 
| 0
 
| 120
 
| 120
Строка 157: Строка 152:
 
|
 
|
 
|-
 
|-
| 7
+
! 7
 
| 0
 
| 0
 
| 720
 
| 720
Строка 169: Строка 164:
 
|
 
|
 
|-
 
|-
| 8
+
! 8
 
| 0
 
| 0
 
| 5040
 
| 5040
Строка 181: Строка 176:
 
|
 
|
 
|-
 
|-
| 9
+
! 9
 
| 0
 
| 0
 
| 40320
 
| 40320
Строка 194: Строка 189:
 
|}
 
|}
  
==Тождества, включающие числа Стирлинга первого рода==
+
==Применение==
 +
 
 +
Равносильное определение получается, если числа Стирлинга задать как коэффициенты в разложении: <tex dpi="130">(x)^{n} = \sum\limits_{k=1}^n s(n,k) x^k,</tex>
 +
 
 +
Следовательно, числа Стирлинга I рода позволяют перейти от базиса <tex dpi="130">(x)^{1},(x)^{2},(x)^{3} \dots </tex> к базису <tex dpi="130">1,x,x^2 \dots </tex> (одно из основных применений)
 +
 
 +
Здесь <tex dpi="130">(x)^{n}</tex> обозначим как возрастающие факториальные степени или символ Похгаммера<ref> [http://ru.wikipedia.org/wiki/Символ_Похгаммера Википедия {{---}} Символ Похгаммера]</ref>:
 +
 
 +
:<tex dpi="130">(x)^{n}=x(x+1)(x+2) \dots (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>
  
Как уже упоминалось ранее:
+
{{Теорема
 +
|statement=
 +
Числа Стирлинга I рода образуют матрицу переходов в линейном пространстве полиномов базиса возрастающих факториальных степеней к базису обычных степеней <tex dpi="130"> \forall n \in \mathbb{N} :  \quad    (x)^{n} = \sum\limits_{k=1}^n s(n,k) x^k</tex>.
 +
|proof=
 +
Индукция по <tex>n</tex>:
 +
 
 +
'''База''': Для <tex>n = 1</tex>, <tex> (x)^{1} = x^{1} </tex> {{---}} очевидно.
 +
 
 +
'''Переход''': Учитывая, что <tex> (x)^{n} = (x)^{n-1} \cdot (x+n-1) </tex> имеем:
 +
 
 +
<tex> (x)^{n} = (x)^{n-1} \cdot (x+n-1) = x \cdot (x)^{n-1} + (n-1) \cdot (x)^{n-1} = </tex> <tex> \sum\limits_{k=1}^{n-1} s(n-1,k) x^{k+1} + \sum\limits_{k=1}^{n-1} s(n-1,k) x^k \cdot (n-1)  </tex>,
 +
 
 +
Введём <tex> t = k + 1 </tex> для первой суммы
 +
 
 +
<tex>\sum\limits_{t=2}^{n} s(n-1,t-1) x^{t} + \sum\limits_{k=1}^{n-1} s(n-1,k) x^k \cdot (n-1)  </tex>
 +
 
 +
При <tex> t = 1 , \quad  \sum\limits_{t=2}^{n} s(n-1,t-1) x^{t} = 0 </tex>,
 +
 
 +
При <tex> k = n , \quad \sum\limits_{k=1}^{n-1} s(n-1,k) x^k \cdot (n-1) = 0 </tex>.
 +
 
 +
Следовательно, мы можем представить выражение в виде одной суммы:
  
:<tex>s(0,0)=1</tex>
+
<tex> \sum\limits_{k=1}^{n} (s(n-1,k-1)+(n-1)s(n-1,k)) \cdot x^{k} = \sum\limits_{k=1}^n s(n,k) x^k</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 dpi = "160">\left[{0\atop 0}\right]=1</tex>
 +
#<tex dpi = "160">\left[{n\atop 0}\right]=\left[{0\atop k}\right]=0</tex>, в общем случае <tex dpi = "160">\left[{n\atop k}\right]=0</tex>, если <tex>k > n</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 dpi="160">\left[{n\atop 1}\right]=(n-1)!</tex>
 +
#:Зафиксируем один элемент, и переставим оставшиеся всеми возможными способами. Повторений не будет, так как чтобы зафиксированный элемент совпал, нужно сдвинуть всю перестановку на <tex dpi = "160">n</tex>, но тогда мы получим исходную перестановку.
 +
#<tex dpi="160">\left[{n\atop n}\right]=1</tex>, очевидно
 +
#<tex dpi="160">\left[{n\atop n-1}\right]={n \choose 2}</tex>
 +
#:Разбить <tex dpi = "160">n</tex> элементов на <tex dpi = "160">n-1</tex> множество можно только одним образом, а именно на множества состоящие из одного элемента и одно множество состоящее из двух. Так как нас интересуют только циклы, получаем выборку двух элементов из всех элементов(множество состоящее из двух элементов всегда является циклом).
 +
#<tex dpi="160">\left[{n\atop n-2}\right]=\frac{1}{4} (3n-1) {n \choose 3}</tex>
 +
#:По аналогии с предыдущим тождеством получаем, что нас интересуют виды конкатенации множеств <tex dpi = "160">((n-4)*1+2+2), ((n-3)*1+3)</tex>. Тогда искомая формула получается упрощением выражения <tex dpi = "160">2! \times {n \choose 3} + \frac{{n \choose 2} \times {n-2 \choose 2}}{2!}</tex>, которая учитывает фиксацию элемента в трехэлементном множестве и повторения двухэлементных.
 +
#<tex dpi="160">\left[{n\atop n-3}\right]={n \choose 2}{n \choose 4}</tex>
 +
#:Аналогично, учитываем только интересующие нас множества и получаем формулу <tex dpi = "160">2! \times {n \choose 2}{n-2 \choose 3} + \frac{{n \choose 2} \times {n-2 \choose 2} \times {n-4 \choose 2}}{3!} + 3! \times {n \choose 4}={n \choose 2}{n \choose 4}</tex>.
  
:<tex>s(n,n-3)={n \choose 2}{n \choose 4}</tex>
+
Для целых, положительных <tex>l,m,n:</tex>
 +
#<tex dpi="160">\left[{n+1\atop m+1}\right]=\sum\limits_{k=1}^n \left[{n\atop k}\right] {k \choose m}=n! \sum\limits_{k=0}^n \frac{\left[{k\atop m}\right]}{k!}  </tex>
 +
#:Второе равенство доказывается путем постепенного спуска вниз:
 +
#:<tex dpi="160">\left[{n+1\atop m+1}\right]=\left[{n\atop m}\right] + n \cdot \left[{n\atop m+1}\right]=\left[{n\atop m}\right] + n \cdot \left(\left[{n-1\atop m}\right] + (n-1) \cdot \left[{n-1\atop m+1}\right]\right)=...=\sum\limits_{k=0}^n \left[{k\atop m}\right]\frac{n!}{k!}=n! \sum\limits_{k=0}^n \frac{\left[{k\atop m}\right]}{k!}</tex>
 +
#:Чтобы доказать первое, будем использовать биекцию(из прошлого раздела) в факториальные степени, а также формулу <tex dpi="160">(x)_{n+1} = x \cdot (x-1)_n \;</tex>.
 +
#:Разложим наше искомое выражение, используя формулу для факториальных степеней, и применив бином Ньютона для второго множителя. Тогда: <tex dpi="160">(x)_{n+1}=\sum_{i=0}^{n}\sum_{k=0}^{i} \left[{n\atop i}\right]\binom{i}{k} x^{k+1}</tex>. Немного преобразовав, получим: <tex dpi="160">(x)_{n+1}=\sum_{k=0}^{n}\sum_{i=k}^{n} \left[{n\atop i}\right]\binom{i}{k} x^{k+1} \;</tex>
 +
#:C другой стороны: <tex dpi="160">(x)_{n+1}=\sum_{k=0}^{n+1} \left[{n+1\atop k}\right] x^k = \sum_{k=0}^{n} \left[{n+1\atop k+1}\right] x^{k+1}</tex>
 +
#:Приравниваем эти два выражения и получаем искомую формулу.
 +
#<tex dpi="160">\left[{n\atop m}\right]=\sum\limits_{k=1}^n \left[{n+1\atop k+1}\right] {k \choose m} (-1)^{m-k} </tex>
 +
#:Доказательство аналогично предыдущему с учетом знакочередования в убывающих факториальных степенях.
 +
#<tex dpi="160">\left[{m+n+1\atop m}\right]=\sum\limits_{k=0}^m (n+k) \left[{n+k\atop k}\right]</tex>
 +
#:Постепенно раскладываем и получаем искомую формулу:
 +
#:<tex dpi="160">\left[{m+n+1\atop m}\right]=\left[{m+n\atop m-1}\right]+\left[{m+n\atop m}\right]\cdot(m+n)=\left[{m+n-1\atop m-2}\right]+\left[{m+n\atop m}\right]\cdot(m+n)+\left[{m+n-1\atop m-1}\right]\cdot(m+n-1)=...=\sum\limits_{k=0}^m (n+k) \left[{n+k\atop k}\right]</tex>
  
 
==Связь между числами Стирлинга==
 
==Связь между числами Стирлинга==
Если числа Стирлинга 1-го рода позволяют перейти от базиса <tex>(x)^{1},(x)^{2},(x)^{3} \cdots</tex> к базису <tex>1,x,x^2 \cdots</tex>,  
+
Если числа Стирлинга I рода позволяют перейти от базиса <tex dpi="130">(x)^{1},(x)^{2},(x)^{3} \dots </tex> к базису <tex dpi="130">1,x,x^2 \dots </tex>,
  
то числа Стирлинга 2-го рода играют обратную роль и позволяют перейти от базиса <tex>1,x,x^2 \cdots</tex> к базису <tex>(x)^{1},(x)^{2},(x)^{3} \cdots</tex>.
+
то [[Числа Стирлинга второго рода|числа Стирлинга II рода]] играют обратную роль и позволяют перейти от базиса <tex dpi="130">1,x,x^2 \dots </tex> к базису <tex dpi="130">(x)^{1},(x)^{2},(x)^{3} \dots </tex>
  
 
Следовательно, числа Стирлинга тесно связаны друг с другом, а их связь выражается формулой:
 
Следовательно, числа Стирлинга тесно связаны друг с другом, а их связь выражается формулой:
  
:<tex>\sum_{k=1}^n S(n,k) s(k,m) (-1)^{k-m} = 1</tex>, если <tex>n=m</tex>, иначе <tex>0</tex>
+
: <p>
 +
 
 +
<tex dpi="130">
 +
\sum\limits_{k=1}^n S(n,k) s(k,m) (-1)^{k-m} =  
 +
\left \{\begin{array}{ll} 1, & n=m \\
 +
0, & \text{otherwise} \end{array} \right.
 +
</tex>
 +
</p>
 +
 
  
 
==См. также==
 
==См. также==
 
* [[Числа Стирлинга второго рода]]
 
* [[Числа Стирлинга второго рода]]
 +
* [[Числа Эйлера I и II рода]]
 +
 +
== Примечания ==
 +
<references/>
 +
 +
==Источники информации==
 +
* [http://ru.wikipedia.org/wiki/Числа_Стирлинга_первого_рода Википедия {{---}} Числа Стирлинга первого рода]
 +
 +
* [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind Wikipedia {{---}} Stirling numbers of the first kind]
  
==Ссылки==
+
* Graham, Knuth, and Patashnik: Concrete Mathematics Second Edition 1994, ISBN 0-201-55802-5 {{---}} 257-267 с.
* [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]
+
* В. Липский: Комбинаторика для программистов 1988,  ISBN 5-03-000979-5 {{---}} 49-50 с.
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Комбинаторика]]
 
[[Категория: Комбинаторика]]

Текущая версия на 19:23, 4 сентября 2022

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

Пример

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

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

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

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

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

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

[math](1; 2)(3; 4)[/math]

[math](1; 4)(2; 3)[/math]

[math](1; 3)(2; 4)[/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]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] можно получить только [math] 3 [/math] разных цикла: [math](1;2;3;4), (1;2;4;3), (1;4;2;3)[/math]. Таким образом, рекуррентность имеет вид:

[math] s(n, k) = \left \{\begin{array}{ll} s(0, 0) = 1, \\ s(n, 0) = 0, & n \gt 0 \\ s(0, k) = 0, & k \gt 0 \\ s(n,k) = s(n-1,k-1)+(n-1)s(n-1,k), & n,k \gt 0 \end{array} \right. [/math]

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

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

По определению, данному выше:
[math](x)^{n+1}=x(x+1)(x+2) \dots (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] увеличатся на [math] 1 [/math], а коэффициенты при этом не изменятся.

Так как левая и правая части равенства равны как полиномы, то равны и коэффициенты перед [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]

Таблица значений

Найдём числовые значения [math]s(n, k)[/math] для малых [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\limits_{k=1}^n s(n,k) x^k,[/math]

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

Здесь [math](x)^{n}[/math] обозначим как возрастающие факториальные степени или символ Похгаммера[1]:

[math](x)^{n}=x(x+1)(x+2) \dots (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]
Теорема:
Числа Стирлинга I рода образуют матрицу переходов в линейном пространстве полиномов базиса возрастающих факториальных степеней к базису обычных степеней [math] \forall n \in \mathbb{N} : \quad (x)^{n} = \sum\limits_{k=1}^n s(n,k) x^k[/math].
Доказательство:
[math]\triangleright[/math]

Индукция по [math]n[/math]:

База: Для [math]n = 1[/math], [math] (x)^{1} = x^{1} [/math] — очевидно.

Переход: Учитывая, что [math] (x)^{n} = (x)^{n-1} \cdot (x+n-1) [/math] имеем:

[math] (x)^{n} = (x)^{n-1} \cdot (x+n-1) = x \cdot (x)^{n-1} + (n-1) \cdot (x)^{n-1} = [/math] [math] \sum\limits_{k=1}^{n-1} s(n-1,k) x^{k+1} + \sum\limits_{k=1}^{n-1} s(n-1,k) x^k \cdot (n-1) [/math],

Введём [math] t = k + 1 [/math] для первой суммы

[math]\sum\limits_{t=2}^{n} s(n-1,t-1) x^{t} + \sum\limits_{k=1}^{n-1} s(n-1,k) x^k \cdot (n-1) [/math]

При [math] t = 1 , \quad \sum\limits_{t=2}^{n} s(n-1,t-1) x^{t} = 0 [/math],

При [math] k = n , \quad \sum\limits_{k=1}^{n-1} s(n-1,k) x^k \cdot (n-1) = 0 [/math].

Следовательно, мы можем представить выражение в виде одной суммы:

[math] \sum\limits_{k=1}^{n} (s(n-1,k-1)+(n-1)s(n-1,k)) \cdot x^{k} = \sum\limits_{k=1}^n s(n,k) x^k[/math]
[math]\triangleleft[/math]

Дополнительные тождества

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

  1. [math]\left[{0\atop 0}\right]=1[/math]
  2. [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]

Также:

  1. [math]\left[{n\atop 1}\right]=(n-1)![/math]
    Зафиксируем один элемент, и переставим оставшиеся всеми возможными способами. Повторений не будет, так как чтобы зафиксированный элемент совпал, нужно сдвинуть всю перестановку на [math]n[/math], но тогда мы получим исходную перестановку.
  2. [math]\left[{n\atop n}\right]=1[/math], очевидно
  3. [math]\left[{n\atop n-1}\right]={n \choose 2}[/math]
    Разбить [math]n[/math] элементов на [math]n-1[/math] множество можно только одним образом, а именно на множества состоящие из одного элемента и одно множество состоящее из двух. Так как нас интересуют только циклы, получаем выборку двух элементов из всех элементов(множество состоящее из двух элементов всегда является циклом).
  4. [math]\left[{n\atop n-2}\right]=\frac{1}{4} (3n-1) {n \choose 3}[/math]
    По аналогии с предыдущим тождеством получаем, что нас интересуют виды конкатенации множеств [math]((n-4)*1+2+2), ((n-3)*1+3)[/math]. Тогда искомая формула получается упрощением выражения [math]2! \times {n \choose 3} + \frac{{n \choose 2} \times {n-2 \choose 2}}{2!}[/math], которая учитывает фиксацию элемента в трехэлементном множестве и повторения двухэлементных.
  5. [math]\left[{n\atop n-3}\right]={n \choose 2}{n \choose 4}[/math]
    Аналогично, учитываем только интересующие нас множества и получаем формулу [math]2! \times {n \choose 2}{n-2 \choose 3} + \frac{{n \choose 2} \times {n-2 \choose 2} \times {n-4 \choose 2}}{3!} + 3! \times {n \choose 4}={n \choose 2}{n \choose 4}[/math].

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

  1. [math]\left[{n+1\atop m+1}\right]=\sum\limits_{k=1}^n \left[{n\atop k}\right] {k \choose m}=n! \sum\limits_{k=0}^n \frac{\left[{k\atop m}\right]}{k!} [/math]
    Второе равенство доказывается путем постепенного спуска вниз:
    [math]\left[{n+1\atop m+1}\right]=\left[{n\atop m}\right] + n \cdot \left[{n\atop m+1}\right]=\left[{n\atop m}\right] + n \cdot \left(\left[{n-1\atop m}\right] + (n-1) \cdot \left[{n-1\atop m+1}\right]\right)=...=\sum\limits_{k=0}^n \left[{k\atop m}\right]\frac{n!}{k!}=n! \sum\limits_{k=0}^n \frac{\left[{k\atop m}\right]}{k!}[/math]
    Чтобы доказать первое, будем использовать биекцию(из прошлого раздела) в факториальные степени, а также формулу [math](x)_{n+1} = x \cdot (x-1)_n \;[/math].
    Разложим наше искомое выражение, используя формулу для факториальных степеней, и применив бином Ньютона для второго множителя. Тогда: [math](x)_{n+1}=\sum_{i=0}^{n}\sum_{k=0}^{i} \left[{n\atop i}\right]\binom{i}{k} x^{k+1}[/math]. Немного преобразовав, получим: [math](x)_{n+1}=\sum_{k=0}^{n}\sum_{i=k}^{n} \left[{n\atop i}\right]\binom{i}{k} x^{k+1} \;[/math]
    C другой стороны: [math](x)_{n+1}=\sum_{k=0}^{n+1} \left[{n+1\atop k}\right] x^k = \sum_{k=0}^{n} \left[{n+1\atop k+1}\right] x^{k+1}[/math]
    Приравниваем эти два выражения и получаем искомую формулу.
  2. [math]\left[{n\atop m}\right]=\sum\limits_{k=1}^n \left[{n+1\atop k+1}\right] {k \choose m} (-1)^{m-k} [/math]
    Доказательство аналогично предыдущему с учетом знакочередования в убывающих факториальных степенях.
  3. [math]\left[{m+n+1\atop m}\right]=\sum\limits_{k=0}^m (n+k) \left[{n+k\atop k}\right][/math]
    Постепенно раскладываем и получаем искомую формулу:
    [math]\left[{m+n+1\atop m}\right]=\left[{m+n\atop m-1}\right]+\left[{m+n\atop m}\right]\cdot(m+n)=\left[{m+n-1\atop m-2}\right]+\left[{m+n\atop m}\right]\cdot(m+n)+\left[{m+n-1\atop m-1}\right]\cdot(m+n-1)=...=\sum\limits_{k=0}^m (n+k) \left[{n+k\atop k}\right][/math]

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

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

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

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

[math] \sum\limits_{k=1}^n S(n,k) s(k,m) (-1)^{k-m} = \left \{\begin{array}{ll} 1, & n=m \\ 0, & \text{otherwise} \end{array} \right. [/math]


См. также

Примечания

Источники информации

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