Что такое перестановка-ожерелье?
Перестановка-ожерелье (её также называют расположением браслета, а в японской традиции — перестановкой «дзюдзу») подсчитывает число различных способов разместить n разных предметов по замкнутому кругу. При этом два расположения считаются одинаковыми, если одно переходит в другое поворотом круга или переворотом (зеркальным отражением). Это на шаг дальше, чем круговая перестановка: круговая перестановка убирает только повороты, а ожерелье вдобавок устраняет и зеркальную симметрию.
Как пользоваться калькулятором
Введите число различных предметов n (неотрицательное целое число), и калькулятор покажет количество различных ожерелий. Для сравнения он также выводит число линейных перестановок (\(n!\)) и круговых перестановок (\((n-1)!\)). Поскольку факториалы растут чрезвычайно быстро, результат вычисляется с помощью точной целочисленной арифметики произвольной точности — поэтому даже при больших значениях n ответ отображается абсолютно точно.
Разбор формулы
Для n предметов в ряд существует \(n!\) упорядочений. Если зафиксировать один предмет на круге, чтобы убрать n равнозначных поворотов, остаётся \((n-1)!\) круговых расположений. В ожерелье узор по часовой стрелке и его зеркальное отражение против часовой стрелки считаются одинаковыми, поэтому мы делим ещё раз на 2:
$$P = \frac{(n-1)!}{2}$$ при \(n \ge 3\).
При n = 0, 1 и 2 простая формула дала бы нецелое число или занизила результат, поэтому по соглашению ответ в каждом из этих случаев равен 1: существует ровно один (или пустой) различный круг.
Разобранный пример
Для n = 5: $$\frac{(5-1)!}{2} = \frac{4!}{2} = \frac{24}{2} = 12$$ различных ожерелий. Для n = 6: \(\frac{5!}{2} = \frac{120}{2} = 60\). Для n = 4: \(\frac{3!}{2} = 3\).
Частые вопросы
Чем это отличается от круговой перестановки? Круговая перестановка равна \((n-1)!\) и считает повороты одинаковыми, но зеркальные отражения — разными. Перестановка-ожерелье делит это число на 2, потому что перевороты тоже считаются одинаковыми.
Почему ответ равен 1 при n = 2? С двумя предметами возможен лишь один круг; поворот или переворот просто меняет местами две позиции, так что все расположения совпадают. Формула \(\frac{(2-1)!}{2} = \frac{1}{2}\) здесь не работает — именно поэтому используется особый случай.
Предполагается ли, что все предметы разные? Да. Этот калькулятор исходит из того, что все n предметов различны. Если часть предметов одинакова, число расположений будет меньше и потребует иного подхода (лемма Бёрнсайда / теория Пойа).
