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