Что такое перестановка ожерелья?
Перестановка ожерелья (в японской терминологии — «дзюдзу дзюнрэцу», или «чёточная перестановка») показывает, сколькими различными способами можно расставить n разных предметов по кругу, если два расположения считаются одинаковыми в случае, когда одно переходит в другое поворотом круга ИЛИ переворотом всего ожерелья (отражением). Этим она отличается от круговой перестановки («эн дзюнрэцу»), где совпадающими считаются только повороты. Это универсальный результат комбинаторики — формула одинакова во всех странах.
Как пользоваться калькулятором
Укажите начальное и конечное значение \(n\) (каждое от 1 до 100), выберите точность отображения в значащих цифрах — и калькулятор выведет по одной строке на каждое целое \(n\) из диапазона вместе с числом перестановок ожерелья. Поскольку эти числа растут факториально, большие значения показываются в научной нотации, округлённой до выбранного числа значащих цифр, а те, что помещаются точно, выводятся полностью.
Разбор формулы
Возьмём все \(n!\) линейных упорядочений из \(n\) различных предметов. Если расставить их по кругу, \(n\) поворотов любого упорядочения становятся неотличимыми, поэтому делим на \(n\) и получаем круговые перестановки: \(n!/n = (n-1)!\). Ожерелье можно также перевернуть, и каждое расположение объединяется со своим зеркальным отражением, поэтому делим ещё на 2: перестановки ожерелья \(= (n-1)!/2\). При \(n = 1\) или \(n = 2\) это не дало бы целого числа, поэтому по соглашению каждому из них соответствует ровно 1 расположение.
$$N(n) = \dfrac{(n-1)!}{2}, \quad n = \text{Start } n \;\ldots\; \text{End } n$$
Разбор на примере
Для диапазона \(n = 3\ldots8\): при \(n=3\) получаем \((3-1)!/2 = 2/2 = 1\); при \(n=4\) — \(6/2 = 3\); при \(n=5\) — \(24/2 = 12\); при \(n=6\) — \(120/2 = 60\); при \(n=7\) — \(720/2 = 360\); при \(n=8\) — \(5040/2 = 2520\). На верхней границе диапазона по умолчанию при \(n=30\) получаем $$29!/2 = 4\,420\,880\,996\,869\,850\,977\,271\,808\,000\,000,$$ то есть примерно \(4{,}42 \times 10^{30}\).
Частые вопросы
Почему делим на 2? Двойка убирает симметрию отражения: перевёрнутое ожерелье выглядит так же, поэтому варианты «по часовой стрелке» и «против часовой стрелки» одного и того же циклического порядка считаются за один.
Почему n=1 и n=2 особые? Общая формула даёт для обоих значение 0,5, а это недопустимое количество; геометрически один или два предмета можно расставить только одним способом, поэтому мы указываем 1.
В чём отличие от круговых перестановок? Круговые перестановки учитывают только повороты и равны \((n-1)!\); перестановки ожерелья дополнительно допускают отражение и при \(n \geq 3\) равны \((n-1)!/2\).
