Числа Стирлинга первого рода (англ. 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] |
Дополнительные тождества
Как уже упоминалось ранее:
- [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]n[/math], но тогда мы получим исходную перестановку.
- [math]\left[{n\atop n}\right]=1[/math], очевидно
- [math]\left[{n\atop n-1}\right]={n \choose 2}[/math]
- Разбить [math]n[/math] элементов на [math]n-1[/math] множество можно только одним образом, а именно на множества состоящие из одного элемента и одно множество состоящее из двух. Так как нас интересуют только циклы, получаем выборку двух элементов из всех элементов(множество состоящее из двух элементов всегда является циклом).
- [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], которая учитывает фиксацию элемента в трехэлементном множестве и повторения двухэлементных.
- [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]
- [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]
- Приравниваем эти два выражения и получаем искомую формулу.
- [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]
- Доказательство аналогично предыдущему с учетом знакочередования в убывающих факториальных степенях.
- [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 с.
