Числа Стирлинга первого рода: перестановки и циклы

Числа Стирлинга первого рода - это коэффициенты, которые связывают два базовых объекта комбинаторики: обычные степени и нисходящий факториал. У них есть наглядный комбинаторный смысл - они считают перестановки с заданным числом циклов. Разберём, чем отличаются знаковая и беззнаковая версии, как работает рекуррентная формула и почему сумма всех чисел в строке равна факториалу. Ниже сразу можно собрать треугольник Стирлинга для нужного $n$ и проверить любое значение.

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

Числа Стирлинга первого рода бывают двух видов - знаковые и беззнаковые. Беззнаковые обозначают $\left[{n \atop k}\right]$ или $c(n, k)$ и определяют как число перестановок множества из $n$ элементов, которые распадаются ровно на $k$ непересекающихся циклов. Это чисто комбинаторная величина, всегда неотрицательная.

Знаковые числа $s(n, k)$ отличаются только множителем $(-1)^{n-k}$:

$$s(n, k) = (-1)^{n-k} \left[{n \atop k}\right].$$

Знаковые версии появляются как коэффициенты при разложении нисходящего факториала по обычным степеням, а беззнаковые - в обратном разложении. Поэтому в задачах на циклы перестановок почти всегда работают с беззнаковыми $\left[{n \atop k}\right]$, а знак подставляют формально, когда нужно алгебраическое тождество.

Рассчитать для своей задачи

Комбинаторный смысл: перестановки и циклы

Любую перестановку можно записать в виде непересекающихся циклов. Например, перестановка $n$ элементов $(1\,3)(2)(4\,5)$ состоит из трёх циклов. Беззнаковое число $\left[{n \atop k}\right]$ как раз и считает, сколько перестановок из $n$ элементов дают ровно $k$ таких циклов.

Крайние случаи запоминаются легко:

• $\left[{n \atop n}\right] = 1$ - единственная перестановка из $n$ неподвижных точек (каждый элемент - отдельный цикл, это тождественная перестановка).
• $\left[{n \atop 1}\right] = (n-1)!$ - перестановки, образующие один большой цикл длины $n$ (циклических расстановок $n$ элементов ровно $(n-1)!$).
• $\left[{n \atop k}\right] = 0$ при $k > n$ и при $k = 0$, $n > 0$ - нельзя получить больше циклов, чем элементов, и нельзя обойтись нулём циклов.

Эта связь с циклами делает числа Стирлинга первого рода естественным инструментом там, где важна структура перестановки, а не просто их количество - в комбинаторике перестановок и в анализе случайных перестановок.

Полезно потренироваться на маленьком примере вручную. Возьмём множество из трёх элементов. Всего перестановок $3! = 6$. Из них на один цикл (расстановка по кругу) приходится $\left[{3 \atop 1}\right] = 2$ перестановки: $(1\,2\,3)$ и $(1\,3\,2)$. На два цикла - $\left[{3 \atop 2}\right] = 3$ перестановки, это все транспозиции с одной неподвижной точкой: $(1\,2)(3)$, $(1\,3)(2)$, $(2\,3)(1)$. И ровно одна перестановка из трёх неподвижных точек даёт три цикла: $\left[{3 \atop 3}\right] = 1$. Сумма $2 + 3 + 1 = 6 = 3!$ - все перестановки распределились по числу циклов без остатка. Именно эту картину строит гистограмма в калькуляторе выше.

Рекуррентная формула

Главный рабочий инструмент - рекуррентное соотношение. Для беззнаковых чисел оно выглядит так:

$$\left[{n \atop k}\right] = \left[{n-1 \atop k-1}\right] + (n-1)\left[{n-1 \atop k}\right].$$

Идея вывода комбинаторная. Рассмотрим $n$-й элемент. Либо он образует собственный цикл-одиночку - тогда оставшиеся $n-1$ элементов должны дать $k-1$ цикл, это слагаемое $\left[{n-1 \atop k-1}\right]$. Либо он встраивается в один из уже имеющихся циклов перестановки $n-1$ элементов с $k$ циклами: вставить новый элемент можно после любого из $n-1$ старых, отсюда множитель $(n-1)$ и слагаемое $(n-1)\left[{n-1 \atop k}\right]$.

Начальные условия: $\left[{0 \atop 0}\right] = 1$, а $\left[{n \atop 0}\right] = 0$ и $\left[{0 \atop k}\right] = 0$ при положительных аргументах. С ними рекуррентность строит весь треугольник снизу вверх.

Рассчитать для своей задачи

Связь с факториалом и нисходящим факториалом

Сумма всех беззнаковых чисел в строке $n$ равна факториалу:

$$\sum_{k=0}^{n} \left[{n \atop k}\right] = n!.$$

Это очевидно из комбинаторного смысла: каждая из $n!$ перестановок имеет какое-то число циклов от $1$ до $n$, и мы просто группируем все перестановки по этому числу. Сумма по всем группам даёт всё множество перестановок.

Алгебраическая роль чисел Стирлинга - разложение факториальных многочленов. Беззнаковые числа дают коэффициенты восходящего факториала:

$$x^{\overline{n}} = x(x+1)\cdots(x+n-1) = \sum_{k=0}^{n} \left[{n \atop k}\right] x^k,$$

а знаковые - нисходящего факториала $x^{\underline{n}} = x(x-1)\cdots(x-n+1)$:

$$x^{\underline{n}} = \sum_{k=0}^{n} s(n, k)\, x^k.$$

Именно поэтому знак вводят как $(-1)^{n-k}$: он переводит коэффициенты восходящего факториала в коэффициенты нисходящего. Числа Стирлинга второго рода делают обратное - раскладывают обычную степень $x^n$ по нисходящим факториалам, и не путать их - частая задача на экзамене.

Проверим разложение нисходящего факториала для $n = 3$. По определению $x^{\underline{3}} = x(x-1)(x-2) = x^3 - 3x^2 + 2x$. Сравнивая с $\sum_k s(3, k)\,x^k$, получаем коэффициенты $s(3,3) = 1$, $s(3,2) = -3$, $s(3,1) = 2$. По модулю это в точности беззнаковые $\left[{3 \atop k}\right] = 1, 3, 2$ из таблицы, а знак чередуется по правилу $(-1)^{n-k}$. Так знаковые и беззнаковые версии оказываются двумя сторонами одного треугольника: одна удобна для подсчёта циклов, другая - для алгебраических преобразований многочленов.

Маленький треугольник значений

Первые строки беззнаковых чисел Стирлинга первого рода удобно держать в голове:

$$\begin{array}{c|cccccc} n \backslash k & 1 & 2 & 3 & 4 & 5 \\ \hline 1 & 1 & & & & \\ 2 & 1 & 1 & & & \\ 3 & 2 & 3 & 1 & & \\ 4 & 6 & 11 & 6 & 1 & \\ 5 & 24 & 50 & 35 & 10 & 1 \\ \end{array}$$

Проверка по рекуррентности: $\left[{4 \atop 2}\right] = \left[{3 \atop 1}\right] + 3\cdot\left[{3 \atop 2}\right] = 2 + 3\cdot 3 = 11$. Сумма строки $n=4$: $6 + 11 + 6 + 1 = 24 = 4!$ - всё сходится. Калькулятор выше строит такой треугольник для любого $n$ и подсвечивает выбранную клетку.

Частые ошибки

• Путают первый и второй род. Первый род считает циклы перестановок и связан с факториальными многочленами; второй род считает разбиения множества на непустые блоки. Это разные треугольники с разными рекуррентностями.
• Забывают множитель $(n-1)$ в рекуррентности. Записывают $\left[{n \atop k}\right] = \left[{n-1 \atop k-1}\right] + \left[{n-1 \atop k}\right]$ как у биномиальных коэффициентов - это неверно, второе слагаемое всегда с весом $(n-1)$.
• Теряют знак. В алгебраических тождествах с нисходящим факториалом нужны именно знаковые $s(n,k)$; подстановка беззнаковых $\left[{n \atop k}\right]$ даёт неправильные коэффициенты при чётном $n-k$ и наоборот.
• Считают $\left[{n \atop 0}\right] = 1$. При $n > 0$ это ноль: перестановка непустого множества не может иметь ноль циклов. Единица только у $\left[{0 \atop 0}\right]$.
• Берут $\left[{n \atop 1}\right] = n!$. Правильно $(n-1)!$ - число циклических расстановок, а не всех перестановок.

FAQ

Чем числа Стирлинга первого рода отличаются от второго? Первый род считает перестановки по числу циклов и участвует в разложении факториальных многочленов. Второй род считает разбиения множества на непустые непомеченные блоки и участвует в разложении степеней через нисходящий факториал. Рекуррентности тоже разные: у второго рода вес $k$, а не $(n-1)$.

Почему числа называют знаковыми и беззнаковыми? Беззнаковые $\left[{n \atop k}\right]$ - это прямой подсчёт перестановок, они всегда положительны. Знаковые $s(n,k) = (-1)^{n-k}\left[{n \atop k}\right]$ нужны в алгебре: только с чередованием знаков коэффициенты дают именно нисходящий факториал $x^{\underline{n}}$.

Как быстро посчитать конкретное число Стирлинга? Через рекуррентность $\left[{n \atop k}\right] = \left[{n-1 \atop k-1}\right] + (n-1)\left[{n-1 \atop k}\right]$, строя треугольник от малых $n$. Для одиночных значений помогают крайние случаи: $\left[{n \atop 1}\right] = (n-1)!$ и $\left[{n \atop n}\right] = 1$.

Коротко

Числа Стирлинга первого рода считают перестановки $n$ элементов по числу циклов: беззнаковое $\left[{n \atop k}\right]$ - это количество перестановок ровно с $k$ циклами, а знаковое $s(n,k) = (-1)^{n-k}\left[{n \atop k}\right]$ возникает как коэффициент нисходящего факториала. Рекуррентность $\left[{n \atop k}\right] = \left[{n-1 \atop k-1}\right] + (n-1)\left[{n-1 \atop k}\right]$ строит весь треугольник, а сумма строки даёт $n!$. Главное - не путать их с числами второго рода и не терять вес $(n-1)$ и знак.