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

Числа Стирлинга первого рода — количество перестановок из n предметов, имеющие ровно k циклов.

Определение

Введём следующее семейство многочленов от x, параметризованное неотрицательным целым числом n:

$(x)_{n}=x(x-1)(x-2)\cdots(x-n+1).$

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

$(x)_{n} = \sum_{k=0}^n S(n,k) x^k.$

Как видно из определения, числа имеют чередующийся знак. Их абсолютные значения задают количество перестановок множества, состоящего из n элементов, в разложении которых на непересекающиеся циклы имеется ровно k циклов.

Рекуррентное соотношение

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

S(n,n) = 1, для n ≥ 0,

S(n,0) = 0, для n > 0,

$S(n, k) = S(n-1, k-1) - (n-1) \cdot S(n-1, k)$ для 0 < k < n.

Пример

Первые ряды:

	0	1	2	3	4	5	6
0	1
1	0	1
2	0	1	1
3	0	1	3	1
4	0	1	7	6	1
5	0	1	15	25	10	1
6	0	1	31	90	65	15	1

Свойства

• $x^n = \sum_{k=0}^n S(n, k) \cdot (x)_k,$ где $(x)_k = x (x-1) \cdots (x-k+1).$
• $S(m,n)=\sum^{m-1}_{i=n-1} \binom{m-1}{i}\,S(i,n-1)$
• $\sum_{m=0}^n S(n,m) = B_n$ — число Белла.

См. также

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

Ссылки

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