Числа Стирлинга первого рода (без знака) — количество перестановок порядка n с k циклами.
Числами Стирлинга первого рода (со знаком) s(n, k) называются коэффициенты многочлена:
где — символ Похгаммера (убывающий факториал):
Как видно из определения, числа имеют чередующийся знак. Их абсолютные значения задают количество перестановок множества, состоящего из n элементов с k циклами.
Рекуррентное соотношение
Числа Стирлинга первого рода задаются рекуррентным соотношением:
, для n ≥ 0,
, для n > 0,
для
- Доказательство.
Для 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 |