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