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

Числа Стирлинга первого рода (без знака) — количество перестановок из n элементов с k циклами.

ОпределениеПравить

Числами Стирлинга первого рода (со знаком) s(n, k) называются коэффициенты многочлена:

$(x{)}_n=\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}s(n,k)x^k,$$(x)_{{n}}=\sum _{{k=0}}^{n}s(n,k)x^{k},$ 

где $(x{)}_n$$(x)_{n}$  — символ Похгаммера (убывающий факториал):

$(x{)}_n=x(x-<!--\; -\; -->1)(x-<!--\; -\; -->2)\cdots <!--\; \cdots \; -->(x-<!--\; -\; -->n+1).$$(x)_{{n}}=x(x-1)(x-2)\cdots (x-n+1).$ 

Как видно из определения, числа имеют чередующийся знак. Их абсолютные значения, называемые числами Стирлинга первого рода без знака, задают количество перестановок множества, состоящего из n элементов с k циклами, и обозначаются $c(n,k)$$c(n,k)$  или $\left[\begin{array}{c}n\\ k\end{array}\right]$${\begin{bmatrix}n\\k\end{bmatrix}}$ :

$c(n,k)=|s(n,k)|=(-<!--\; -\; -->1{)}^{n-<!--\; -\; -->k}s(n,k).$$c(n,k)=|s(n,k)|=(-1)^{n-k}s(n,k).$ 

Их производящей функцией является возрастающий факториал:

$\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}c(n,k)x^k=x(x+1)(x+2)\cdots <!--\; \cdots \; -->(x+n-<!--\; -\; -->1)=x^{\stackrel{¯<!--\; ¯\; -->}{n}}=(x+n-<!--\; -\; -->1{)}_n.$$\sum _{k=0}^{n}c(n,k)x^{k}=x(x+1)(x+2)\cdots (x+n-1)=x^{\bar {n}}=(x+n-1)_{n}.$ 

Рекуррентное соотношениеПравить

Числа Стирлинга первого рода задаются рекуррентным соотношением:

$s(0,0)=c(0,0)=1$$s(0,0)=c(0,0)=1$ ,

$s(n,0)=c(n,0)=0$$s(n,0)=c(n,0)=0$ , для n > 0,

$s(0,k)=c(0,k)=0$$s(0,k)=c(0,k)=0$ , для k > 0,

для чисел со знаком: $s(n,k)=s(n-<!--\; -\; -->1,k-<!--\; -\; -->1)-<!--\; -\; -->(n-<!--\; -\; -->1)\cdot <!--\; \cdot \; -->s(n-<!--\; -\; -->1,k)$$s(n,k)=s(n-1,k-1)-(n-1)\cdot s(n-1,k)$  для $0<k<n.$ 

для чисел без знака: $c(n,k)=c(n-<!--\; -\; -->1,k-<!--\; -\; -->1)+(n-<!--\; -\; -->1)\cdot <!--\; \cdot \; -->c(n-<!--\; -\; -->1,k)$$c(n,k)=c(n-1,k-1)+(n-1)\cdot c(n-1,k)$  для $0<k<n.$ 

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

Для n=1 это равенство проверяется непосредственно. Пусть перестановка (n-1)-го порядка распадается на k циклов. Число n можно добавить после любого числа в соответствующий цикл. Все полученные перестановки различны и содержат k циклов, их количество (n-1)·s(n-1, k). Из любой перестановки (n-1)-го порядка, содержащей k-1 цикл, можно сформировать единственную перестановку n порядка, содержащую k циклов, добавив цикл образованный единственным числом n. Очевидно, что эта конструкция описывает все перестановки n-го порядка, содержащие k циклов. Тем самым равенство доказано.

ПримерПравить

Первые числа Стирлинга со знаком:

n\k	0	1	2	3	4	5	6
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

См. такжеПравить

• Число Стирлинга второго рода
• Факториал
• Субфакториал

СсылкиПравить

• Д. Белешко Комбинаторика (часть 2). СПбГУ ИТМО.