Изменения
→Алгоритм решения задачи про ожерелья
{{ОпределениеЗадача
|definition=
Требуется посчитать количество ожерелий из <tex>n</tex> бусинок, каждая из которых может быть покрашена в один из <tex> k </tex> цветов. При сравнении двух ожерелий их можно поворачивать, но не переворачивать (т.е. разрешается сделать циклический сдвиг).}}
Решение этой задачи опирается на [[Лемма Бёрнсайда и Теорема Пойа|лемму Бернсайда Бёрнсайда и теорему Пойа]].
<tex> |C | = </tex> <tex dpi = "180">\fracdfrac{1} {|G|}</tex><tex>\sum\limits_{k l \in G}I(k)</tex>. Где <tex>I^{P(kl)</tex> - количество неподвижных точек для перестановки <tex>k</tex>.|proof=Рассмотрим сумму в числителе дроби справа:<tex>\sum\limits_{k \in G}I(k)</tex> — это ни что иное как количество "инвариантных пар". Очевидно, что в формуле мы имеем право изменить порядок суммирования - сделать внешнюю сумму по элементам множества <tex>f</tex>, а внутри нее поставить величину <tex>J(f)</tex> — количество перестановок, относительно которых объект <tex>f</tex> инвариантен:
По условию, перестановкой инвариантной данной будет любая перестановка, полученная из данной циклическим сдвигом.
Очевидно, что для каждой перестановки длины <tex>n</tex> существует ровно <tex>n - 1</tex> инвариантная перестановка, то есть всего инвариантных перестановок в каждом классе <tex>n</tex>, теперь найдем <tex>P(i)</tex>. Заметим, что в <tex>i</tex>-ой перестановке на <tex>l</tex>-ой позиции стоит элемент <tex>(i + l)\bmod n</tex>. Также, заметим, что элемент <tex>a</tex> переходит в элемент <tex>a + in</tex>, где <tex>i = 1, 2, \ldots k</tex>. Из этого следует, что длина цикла для <tex>i</tex>-ой перестановки равна <tex> \dfrac{\mathrm{lcm}(n, i)}{i} = \dfrac{n}{\mathrm{gcd}(i,n)}</tex>, где <tex>\mathrm{gcd}(i, n)</tex> {{---}} [[Наибольший общий делитель|НОД<tex>(i, n)</tex>]], <tex>\mathrm{lcm}(i, n)</tex> {{---}} [[Наименьшее общее кратное|НОК<tex>(i, n)</tex>]]. Откуда следует что:
<tex >|C | =</tex> <tex dpi = "180"> \fracdfrac{1} {|G|n}</tex><tex>\sum\limits_{fi = 1}^{n} k^{\mathrm{gcd} J(fi,n)}</tex>.
Для начала покажем, что в качестве операций требуется рассматривать только повороты и отражения.
* Поворот и отражение {{---}} отражение.
Занумеруем наши бусинки по часовой стрелке. Поворот и отражение не меняют порядка (в каком-то направлении бусинки занумерованы по порядку). Нетрудно понять, что отражение меняет направление обхода наших бусинок и не меняет порядка. Если мы сначала сделаем поворот, а потом отразим относительно какой-нибудь оси, то мы то самое же можем получить и обыкновенным отражением относительно какой-то оси. Такая ось найдётся, потому что всегда можно выбрать ось, что поставит первую бусинку на своё изначальное место, поменяв направление обхода (если перебирать все оси подряд, начиная с оси, проходящей через нужную нам бусинку, то изначально она останется на своём месте, потом сместится на одно место, потом на два и.т.д.). Поэтому поворот и отражение не добавляет нам новой операции.
Пусть нам даны бусинки число бусинок нечётное, тогда мы имеем <tex>n</tex> осей, проходящих через каждую бусинку. Рассмотрим одну ось. Возьмём половину бусинок с одной стороны от оси и ту бусинку, через которую проходит данная ось. Мы можем окрасить их в произвольные цвета, а остальная половина по ним однозначно восстановится. Таким образом количество неподвижных точек для одной оси будет <tex>k различных цветов^{\frac{n + 1}{2}}</tex>. Операций в группе будет в два раза больше, а ожерелье должно состоять из чем было: <tex>2n</tex> (<tex>n</tex> сдвигов и <tex>n бусинок</tex> отражений).
<tex> |G| = 2n</tex>. Первые <tex>n</tex> операций {{---}} повороты, и сумма количества их неподвижных точек, делённая на <tex>2n</tex>, принимает значение <tex>\dfrac{|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>|B| = \dfrac{|C =</tex> <tex dpi = "180"> |}{2} + \dfrac{1}{2n}k^{\fracdfrac{n + 1} {2}}n = \dfrac{|GC|}{2} + \dfrac{1}{2}k^{\dfrac{n + 1}{2}}</tex><tex>= \dfrac{1} {2n}\sum\limits_{l q|n}\varphi\left(\dfrac{n}{q}\in Gright)k^q + \dfrac{1}{2} k^{P(l)\dfrac{n + 1}{2}}</tex>
<tex>|B| = \dfrac{|C|}{2} + \dfrac{1}{2n}\left(\dfrac{n}{2}k^{\frac{n}{2}} + \dfrac{n}{2}k^{\frac{n}{2} + 1}\right)</tex> <tex>= \dfrac{|C|}{2} + \dfrac{1}{4}k^{\frac{n}{2}}(k + 1) = \dfrac{1} {2n}\sum\limits_{q|n}\varphi\left(\dfrac{n}{q}\right)k^q + \dfrac{1}{4}k^{\frac{n}{2}}(k+1)</tex>
== Примечания ==
<references/>
==CсылкиИсточники информации ==* [https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A0%D0%B5%D0%B4%D1%84%D0%B8%D0%BB%D0%B4%D0%B0_%E2%80%94_%D0%9F%D0%BE%D0%B9%D0%B0#.D0.97.D0.B0.D0.B4.D0.B0.D1.87.D0.B0_.D0.BE_.D0.BA.D0.BE.D0.BB.D0.B8.D1.87.D0.B5.D1.81.D1.82.D0.B2.D0.B5_.D0.BE.D0.B6.D0.B5.D1.80.D0.B5.D0.BB.D0.B8.D0.B9 Википедия {{---}} Теорема Редфилда — Пойа, Задача о количестве ожерелий]*[http://e-maxx.ru/algo/necklace_colouring MAXimal::algo::Ожерелья]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Теория групп]]