Все формулы РФ

Математика / Графы, логика

Круговые перестановки: рассадка за круглым столом

Число круговых перестановок n различных объектов равно (n−1)!, если повороты всей расстановки считаются одинаковыми. Зеркальное отражение при этом обычно даёт другой порядок соседей.

Опубликовано: Обновлено:

КомбинаторикаДискретная математикаАлгебраСтраницы с задачами и решениями

Формула

$$P_{\mathrm{circle}}(n)=\frac{n!}{n}=(n-1)!,\qquad n\ge1$$
Схема Повороты и отражение трёх гостей
Повороты и отражение трёх гостейПовороты и отражение трёх гостейПорядокПоворот 1Поворот 2Поворот 3По кругуABCBCACABОбратныйACBCBABACABC и ACB не совмещаются поворотом

Два класса по три поворота: 3! / 3 = 2.

Обозначения

$Pcircle$
число различных круговых порядков, безразмерная величина
$n$
число различных объектов, безразмерная величина

Условия применения

Все объекты различимы, используются ровно один раз, n≥1. У круга нет выделенного места или фиксированной метки. Две расстановки одинаковы только тогда, когда совмещаются поворотом; отражения не отождествляются. Дополнительных ограничений на соседство нет.

Ограничения

При нумерованных стульях считаются n! рассадок, поскольку поворот меняет места людей. Для браслетов с допустимым переворачиванием нужны дополнительные отождествления. Если объекты повторяются, размеры классов поворота могут различаться, и простое деление на n уже не гарантировано.

Подробное объяснение

Разрежем круг в одном месте и запишем объекты в линейный ряд по часовой стрелке. Всего рядов n!, но один круг даст n разных рядов: начало можно выбрать у любого из n объектов. Поскольку все объекты различны, эти n записей действительно различны и повторов меньшего периода нет.

Каждый круг посчитан одинаковое число раз, поэтому делим n! на n. Такой вывод является применением правила деления на размер класса равнозначных записей. Важно, что равенство размеров классов здесь обосновано различимостью всех объектов, а не просто наличием круглого рисунка.

Есть и более короткий способ: закрепить одного выбранного гостя как начало обхода. Оставшихся n−1 человек размещаем по порядку относительно него, получая (n−1)! вариантов. Закрепление не назначает реальный номер стулу, а выбирает представителя каждого класса поворотов.

Зеркальное отражение меняет порядок обхода: у фиксированного гостя левый и правый соседи меняются местами. Для обычной рассадки это другой вариант. Поэтому деление ещё на два в формуле отсутствует. Если условие задачи разрешает отражения, такую симметрию нужно оговорить отдельно.

При двух гостях существует один круговой порядок, при трёх — два. Результат не зависит от диаметра стола или расстояний между стульями: считаются отношения порядка, а не геометрические координаты. Запрет соседства двух людей потребует выделить и вычесть запрещённые варианты.

Как пользоваться формулой

  1. Проверьте отсутствие нумерации мест: поворот всей рассадки должен сохранять один и тот же вариант.
  2. Убедитесь, что все гости различимы и отражение круга не входит в разрешённые отождествления.
  3. Зафиксируйте одного участника как начало обхода и переставьте остальных n−1 человек по кругу.
  4. Вычислите факториал n−1 и отдельно проверьте дополнительные требования к соседству или местам.

Историческая справка

Круговые перестановки служат классическим учебным примером подсчёта с точностью до симметрии. В современной дискретной математике такой подсчёт объясняют через классы эквивалентности: несколько линейных записей описывают один круговой порядок. Открытый учебник Оскара Левина использует рассадку вокруг стола в разделе о принципе деления. Этот подход показывает связь элементарного факториала с более общим языком действий групп и симметрий, получившим систематическое развитие в математике XIX–XX веков. Простой случай различных гостей обходится без специальных теорем: все классы имеют один размер. При повторяющихся цветах этот аргумент перестаёт работать, и требуется более общий учёт неподвижных конфигураций. Формуле не назначается единственный изобретатель рассадки за столом.

Историческая линия формулы

Результат (n−1)! — стандартное следствие принципа деления для перестановок различных объектов. Здесь используется только группа поворотов круга. Историческая связь с теорией симметрий объясняет метод, но не означает, что любое расположение по окружности автоматически имеет такое количество вариантов.

Пример

Шесть разных участников садятся за круглый стол без выделенного места. Две рассадки считаются одинаковыми, если каждый сохранил порядок соседей по часовой стрелке после общего поворота. Закрепим участника A как начало записи: остальных пятерых можно упорядочить 5! = 120 способами. Значит, круговых рассадок 120. Независимая проверка через пронумерованные места даёт 6! = 720 вариантов; каждому круговому порядку соответствуют шесть поворотов, поэтому 720/6 = 120. Отражения не убираем, поскольку они меняют левую и правую стороны. Ответ измеряется числом рассадок, а не числом пар соседей.

Частая ошибка

Не делите на n, если места имеют номера или один стул выделен для председателя. Не делите дополнительно на два без условия об отражениях. Не применяйте формулу к одинаковым бусинам: у них возможны повторяющиеся рисунки. Не путайте закрепление гостя для подсчёта с ограничением физического места.

Практика

Задачи с решением

Четыре гостя

Условие. Сколько круговых рассадок четырёх разных гостей без нумерации мест?

Решение. Закрепляем одного гостя, переставляем трёх: 3! = 6.

Ответ. 6 рассадок

Нумерованные места

Условие. Пять гостей занимают пять пронумерованных стульев. Сколько рассадок?

Решение. Повороты различимы по номерам стульев, поэтому считаем 5! = 120, а не 4!.

Ответ. 120 рассадок

Дополнительные источники

  • https://discrete.openmathbooks.org/more/mdm/sec_basic-quotient.html
  • https://math.mit.edu/~rstan/ec/ec1.pdf

Связанные формулы

Математика

Число перестановок без повторений

$P_n=n!$

Формула описывает прием «перестановки разных объектов» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Математика

Перестановки с повторениями: одинаковые элементы

$P=\frac{n!}{n_1!n_2!\cdots n_r!},\qquad n_1+\cdots+n_r=n$

Число различных упорядоченных записей из заданного набора элементов, среди которых есть одинаковые. Формула делит все перестановки на перестановки внутри каждой группы неразличимых элементов.

Математика

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

$c(n,k)=c(n-1,k-1)+(n-1)c(n-1,k)$

Беззнаковые числа Стирлинга первого рода считают перестановки n различных элементов, состоящие ровно из k циклов. Рекурсия отделяет новый одноэлементный цикл от вставки элемента в существующий цикл.