Математика · объяснение и практика
Числа Стирлинга первого рода: считаем перестановки по числу циклов
Переводим перестановку в непересекающиеся направленные циклы, доказываем рекурсию вставкой нового элемента и отличаем циклический порядок от неупорядоченной группы.

В теме Доказательства и комбинаторные модели · Учебная карта
Главная мысль
Беззнаковое число Стирлинга c(n,k) равно числу перестановок n различимых элементов с ровно k непересекающимися циклами, включая неподвижные элементы. Новый элемент либо образует одиночный цикл, либо вставляется после одного из n−1 прежних элементов: c(n,k)=c(n−1,k−1)+(n−1)c(n−1,k).
Цикл задаёт следующего, а не только состав группы
Перестановку удобно понимать как взаимно однозначное отображение множества на себя. Если последовательно применять его к одному элементу, мы вернёмся к началу; получится направленный цикл. Из ещё не посещённого элемента начинается следующий цикл. Каждый элемент встречается ровно в одном из них, а неподвижный элемент записывается циклом длины один.
Записи (1 3 2) и (3 2 1) задают одно отображение: изменилось только начало чтения. Но (1 2 3) задаёт другое направление переходов. Порядок непересекающихся циклов при записи несущественен. В отличие от обычного блока множества цикл сохраняет внутренний круговой порядок: на трёх элементах один блок единственен, а направленных циклов два. Поэтому числа первого и второго рода нельзя подменять друг другом.
Вставка после элемента обратима удалением
Пусть новый элемент n образует цикл (n). Удалив этот цикл, получим перестановку n−1 элементов с k−1 циклами. Это первый вклад c(n−1,k−1). Во втором случае цикл с n длиннее единицы. В прежней перестановке выберем элемент a и заменим переход a→b двумя переходами a→n→b. Число циклов сохранится.
Выборов a ровно n−1 во всей перестановке, независимо от числа циклов и их длин. Обратно в полученном цикле у n есть единственный предшественник a; удаление n и соединение a с его прежним следующим восстанавливает исходную пару «перестановка, место вставки». Никакие два места не склеиваются. Поэтому второй вклад равен (n−1)c(n−1,k), а не kc(n−1,k). Условие c(0,0)=1 и нули за допустимой треугольной областью позволяют строить таблицу.
Пример
Найдите число перестановок четырёх элементов с двумя циклами. Используйте c(3,1)=2 и c(3,2)=3.
Новый отдельный цикл (4) даёт две перестановки. Вставка 4 в одну из трёх стрелок каждой из трёх перестановок с двумя циклами даёт девять. Итого c(4,2)=2+3·3=11. Подсчёт можно сверить по типам: три разбиения на пары дают три перестановки типа 2+2, а выбор неподвижного элемента и одного из двух трёхциклов даёт восемь типа 3+1.
Проверяем края и смысл суммы по всем циклам
При n≥1 один цикл длины n можно начинать с элемента 1. Остальные n−1 элементов располагаются после него в любом порядке, поэтому c(n,1)=(n−1)!. При k=n все элементы неподвижны, и c(n,n)=1. Сумма c(n,k) по всем допустимым k равна n!, потому что каждая перестановка имеет единственное число циклов. Это проверка полноты распределения, а не равенство каждого его слагаемого факториалу.
Иногда первыми числами Стирлинга называют знаковые величины s(n,k)=(−1)ⁿ⁻ᵏc(n,k). В нашем подсчёте используются только беззнаковые c, поэтому отрицательных количеств нет. При чтении таблицы необходимо сверить соглашение. Рассадка за неподписанными круглыми столами тоже моделируется циклами, если различается направление соседства и поворот одного стола не создаёт нового варианта; при отождествлении зеркальных рассадок счёт уже изменится.
При n−1 циклах ровно один цикл имеет длину два, а остальные являются одиночными. Поэтому здесь c(n,n−1)=C(n,2): выбирается переставляемая пара. Но совпадение этого края с числами второго рода не распространяется на таблицу целиком. Уже при трёх элементах один направленный цикл имеет два варианта, а один неподписанный блок — только один.
От чтения к действию
А теперь — вы
Частые вопросы
Поворот записи цикла считается новым вариантом?
Нет. Начальная точка записи не меняет отображение элемента в следующий. Изменение направления при длине хотя бы три обычно меняет перестановку.
Почему мест вставки больше, чем циклов?
Вставка производится после конкретного элемента. Цикл длины r имеет r разных стрелок, а сумма длин всех прежних циклов равна n−1.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как посчитать все порядки разных предметов
Считаем линейные порядки всех разных предметов, объясняем убывание числа вариантов на каждом месте и учитываем простое ограничение соседства как блок.
Открыть темуПочему разбиения числа отличаются от упорядоченных сумм
Как считать разбиения числа на положительные слагаемые без порядка, отличать их от композиций и не делить автоматически число упорядоченных сумм на факториал.
Открыть темуКак взаимно однозначное соответствие доказывает равенство количеств
Как доказать равенство количеств без прямого перечисления, построить обратное соответствие и заметить потерянные или склеенные объекты при кодировании.
Открыть тему