Изменения
→Алгоритм решения задачи про ожерелья с отражениями
== Алгоритм решения задачи про ожерелья с отражениями==
[[Файл:axis_of_braclets.png|300px|thumb|right|слева Слева пример оси для нечётного случая, справа . Справа для чётного.]]
Пусть теперь ожерелья считаются одинаковыми, если они не только переходят друг в друга поворотом, но и отражением относительно некоторой оси (ось может проходить через две противоположные бусинки или через две противоположные пустоты в чётном случае и через бусинку и пустоту напротив неё в нечётном случае). Такие ожерелья называются bracelets <ref>[https://en.wikipedia.org/wiki/Necklace_(combinatorics) Necklace (combinatorics)]</ref>.
Будем пользоваться [[Лемма Бёрнсайда и Теорема Пойа|леммой Бёрнсайда]].
Для начала покажем, что в качестве операций требуется рассматривать только повороты и отражения.
* Поворот и отражение {{- --}} отражение.
Занумеруем наши бусинки по часовой стрелке. Поворот и отражение не меняют порядка (в каком-то направлении бусинки занумерованы по порядку). Нетрудно понять, что отражение меняет направление обхода наших бусинок и не меняет порядка. Если мы сначала сделаем поворот, а потом отразим относительно какой-нибудь оси, то мы то самое же можем получить и обыкновенным отражением относительно какой-то оси. Такая ось найдётся, потому что всегда можно выбрать ось, что поставит первую бусинку на своё изначальное место, поменяв направление обхода (если перебирать все оси подряд, начиная с оси, проходящей через нужную нам бусинку, то изначально она останется на своём месте, потом сместится на одно место, потом на два и.т.д.). Поэтому поворот и отражение не добавляет нам новой операции.
* Отражение и поворот {{- --}} отражение.
Аналогичные рассуждения.
* Отражение и отражение {{- --}} поворот.
Тут мы дважды меняем направление обхода, но не меняем порядка. Поэтому данная операция заменяется обычным поворотом.
<tex> |B| = </tex> <tex dpi = "140">\frac{1} {|G|}</tex><tex>\sum\limits_{k \in G}I(k)</tex>
<tex> |G| = 2n</tex>. Первые <tex>n</tex> операций {{--- } повороты, и сумма количества их неподвижных точек, делённая на <tex>2n</tex>, принимает значение <tex>\frac{|C|} {2}</tex>, где <tex>|C|</tex> - количество ожерелий из <tex>n</tex> бусинок <tex>k</tex> различных цветов без отражений (задача выше) т.к. деление в задаче без отражений происходило на <tex>n</tex>, а здесь на <tex>2n</tex>. Следующие <tex>n</tex> операций {{- --}} отражения. У каждой такой операции <tex>k^{\frac{n + 1}{2}}</tex> неподвижных точек. Поэтому сумма получается <tex>k^{\frac{n + 1}{2}}n</tex>.
<tex dpi = "140">|B| = \frac{|C|}{2} + \frac{1}{2n}k^{\frac{n + 1}{2}}n = \frac{|C|}{2} + \frac{1}{2}k^{\frac{n + 1}{2}} </tex><tex dpi = "140"> = \frac{1} {2n}\sum_sum\limits_{q|n}\phivarphi(\frac{n/}{q})k^q + \frac{1}{2}k^{\frac{n + 1}{2}} </tex>
По Лемме Бёрнсайда:
<tex dpi = "140">|B| = \frac{|C|}{2} + \frac{1}{2n}(\frac{n}{2}k^{\frac{n}{2}} + \frac{n}{2}k^{\frac{n}{2} + 1})</tex> <tex dpi = "140">= \frac{|C|}{2} + \frac{1}{4}k^{\frac{n}{2}}(k + 1) = \frac{1} {2n}\sum_sum\limits_{q|n}\phivarphi(\frac{n/}{q})k^q + \frac{1}{4}k^{\frac{n}{2}}(k+1)</tex>
== См. также ==
