Изменения
Нет описания правки
== Алгоритм решения задачи про ожерелья с отражениями==
Пусть теперь ожерелья считаются одинаковыми, если они не только переходят друг в друга поворотом, но и отражением относительно некоторой оси(ось может проходить через две противоположные бусинки в чётном случае и через бусинку и пустоту напротив неё в нечётном случае). Такие ожерелья называются [https://en.wikipedia.org/wiki/Necklace_(combinatorics) bracelets].
Будем пользоваться [[Лемма Бёрнсайда и Теорема Пойа|леммой Бёрнсайда]].
Разберём два случая.
Для начала покажем, что в качестве операций требуется рассматривать только повороты и отражения.
* Поворот и отражение - отражение.
Занумеруем наши бусинки по часовой стрелке. Поворот и отражение не меняют порядка (в каком-то направлении бусинки занумерованы по порядку). Нетрудно понять, что отражение меняет направление обхода наших бусинок и не меняет порядка. Если мы сначала сделаем поворот, а потом отразим относительно какой-нибудь оси, то мы то самое же можем получить и обыкновенным отражением. Надо просто найти такую ось, что вернёт первую бусинку на своё место, вместе с этим и поменяется и направление обхода, что вернёт всё на своё место, то есть отразив изначально относительно данной оси мы бы получили данное ожерелье. Такая ось найдётся, потому что всегда можно выбрать такую ось, что поставит нужную нам бусинку в любое место, поменяв направление обхода (если перебирать все оси подряд, начиная с оси, проходящей через нужную нам бусинку, то изначально она останется на своём месте, потом сместится на одно место, потом на два и.т.д.). Поэтому поворот и отражение не добавляет нам новой операции.
* Отражение и поворот - отражение.
Аналогичные рассуждения.
* Отражение и отражение - поворот.
Тут мы дважды меняем направление обхода, но не меняем порядка. Поэтому данная операция заменяется обычным поворотом.
Пусть число бусинок нечётное, тогда мы имеем <tex>n</tex> осей, проходящих через каждую бусинку. Рассмотрим одну ось. Возьмём половину бусинок с одной стороны от оси и ту бусинку, через которую проходит данная ось. Мы можем окрасить их в произвольные цвета, а остальная половина по ним однозначно восстановится. Таким образом количество неподвижных точек для одной оси будет <tex>k^{\frac{n + 1}{2}}</tex>.
