Математика / Графы, логика
Числа Стирлинга первого рода: циклы перестановки
Беззнаковые числа Стирлинга первого рода считают перестановки n различных элементов, состоящие ровно из k циклов. Рекурсия отделяет новый одноэлементный цикл от вставки элемента в существующий цикл.
Формула
Все четыре класса в сумме дают 4! = 24.
Обозначения
- $c(n,k)$
- число перестановок с k циклами, безразмерная величина
- $n$
- число различимых элементов, безразмерная величина
- $k$
- число циклов, включая одноэлементные, безразмерная величина
Условия применения
n и k — неотрицательные целые. Начало таблицы c(0,0)=1; при n>0 имеем c(n,0)=0, а при k>n — ноль. Циклические сдвиги записи одного цикла равнозначны, порядок самих циклов не учитывается. Направление обхода цикла сохраняется.
Ограничения
Речь идёт о беззнаковых числах c(n,k). Знаковые числа часто обозначают s(n,k)=(-1)^(n−k)c(n,k); подставлять их в подсчёт количества без изменения знака нельзя. Не путайте циклы с группами Стирлинга второго рода: группа из трёх элементов допускает два циклических порядка.
Подробное объяснение
Каждая перестановка раскладывается на непересекающиеся циклы. Цикл (1 3 2) означает переходы 1→3, 3→2, 2→1; неподвижный элемент записывают отдельным циклом. Число c(n,k) различает перестановки, но отбирает только те, у которых получилось ровно k таких циклов.
Посмотрим на последний элемент n. Если он образует самостоятельный цикл, остальные n−1 элементов должны иметь k−1 циклов. Это даёт первое слагаемое. Если его цикл длиннее одного, удалим n и соединим его предшественника с последующим элементом: останется перестановка с k циклами.
Чтобы восстановить второй случай, можно вставить n после любого из n−1 элементов. Важно считать места после элементов, а не число циклов: длинный цикл даёт больше мест вставки, чем короткий. Поэтому множитель равен n−1 независимо от распределения длин циклов.
Граничные значения имеют простой смысл. При k=n каждый элемент неподвижен, так что c(n,n)=1. При k=1 все элементы образуют один цикл, и вариантов (n−1)!. Сумма по всем k равна n!, поскольку любая перестановка имеет какое-то определённое число циклов.
Таблицу удобно строить по строкам с нулевой строкой в качестве базы. Слагаемые берутся только из предыдущей строки, что позволяет вычислять значения без перебора всех n! перестановок. Для ручной проверки малых строк полезно отдельно разобрать типы длин циклов.
Как пользоваться формулой
- Уточните, что требуется число циклов перестановки, а не число обычных непустых подмножеств.
- Запишите нулевую строку c(0,0)=1 и нули вне диапазона от нуля до текущего размера множества.
- Вычисляйте новую строку из предыдущей: левое значение плюс n−1, умноженное на значение над ним.
- Проверьте крайние элементы строки и её сумму n!, чтобы обнаружить ошибку множителя или индекса.
Историческая справка
Имя Джеймса Стирлинга связано с классическими числами, появляющимися при переходе между обычными степенями и факториальными многочленами. Современная комбинаторика различает первый и второй род, а также знаковые и беззнаковые соглашения. В книге Ричарда Стэнли Enumerative Combinatorics и в NIST DLMF эти соглашения явно разделены. Для задач о перестановках удобнее положительные количества c(n,k); для коэффициентов падающего факториала естественно появляются чередующиеся знаки. Эта разница объясняет, почему в справочных таблицах с одинаковым именем можно встретить отрицательные значения. Развитие обозначений и интерпретаций продолжалось в комбинаторной литературе XX века; историческое имя не отменяет необходимости сначала прочитать определение конкретного источника.
Историческая линия формулы
Здесь используются беззнаковые числа Стирлинга первого рода с интерпретацией через циклы перестановки. Их не следует смешивать со знаковыми коэффициентами s(n,k) и числами Стирлинга второго рода. Рекурсия доказана разбором положения нового элемента и не требует исторических предположений.
Пример
Сколько перестановок четырёх элементов имеют ровно два цикла? В предыдущей строке c(3,1)=2 и c(3,2)=3. Рекурсия даёт c(4,2) = 2 + 3·3 = 11. Проверим по длинам циклов. Тип 3+1: выбираем неподвижный элемент четырьмя способами, а остальные три образуют один цикл двумя способами, всего 8. Тип 2+2: четыре элемента разбиваются на две пары тремя способами, каждая пара задаёт единственный двухэлементный цикл, всего 3. Сумма 8 + 3 = 11 совпала с рекурсией. Это количество перестановок без физических единиц. Порядок записи двух циклов не удваивает ответ.
Частая ошибка
Не используйте множитель k вместо n−1: это рекурсия другого рода. Не считайте (1 2 3) и (2 3 1) разными циклами. Но (1 3 2) отличается от (1 2 3), поскольку направление переходов изменилось. Не исключайте неподвижные элементы: каждый из них добавляет один цикл.
Практика
Задачи с решением
Один цикл
Условие. Сколько перестановок пяти элементов состоят из одного цикла?
Решение. c(5,1) = (5−1)! = 4! = 24.
Ответ. 24 перестановки
Три цикла
Условие. Вычислите c(4,3), используя c(3,2) = 3 и c(3,3) = 1.
Решение. c(4,3) = 3 + (4−1)·1 = 6. Это также выбор одной пары для единственного цикла длины 2.
Ответ. 6 перестановок
Дополнительные источники
- https://dlmf.nist.gov/26.8
- https://math.mit.edu/~rstan/ec/ec1.pdf
Связанные формулы
Математика
Число перестановок без повторений
Формула описывает прием «перестановки разных объектов» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.
Математика
Числа Стирлинга второго рода: разбиение на группы
Число Стирлинга второго рода S(n,k) показывает, сколькими способами можно разбить n различных элементов на k непустых неименованных групп. Рекурсия отделяет добавление элемента в старую группу от создания новой.
Математика
Круговые перестановки: рассадка за круглым столом
Число круговых перестановок n различных объектов равно (n−1)!, если повороты всей расстановки считаются одинаковыми. Зеркальное отражение при этом обычно даёт другой порядок соседей.