Изменения

<tex>|C| =</tex> <tex dpi = "180"> \fracdfrac{1} {|G|}</tex><tex>\sum\limits_{l \in G} k^{P(l)}</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} {n}</tex><tex>\sum\limits_{i = 1}^{n} k^{\mathrm{gcd}(i,n)}</tex>.

где <tex>|C|</tex> {{- --}} кол-во различных ожерелий,которые можно составить из <tex>n</tex> бусинок <tex>k</tex> различных цветов.

Если раскраски ожерелья одинаковые, то они принадлежат одной [[Орбита|орбите]], т.е. одна получается из другой некоторым преобразованием симметрии. Неподвижные точки поворота есть только у тождественного поворота и их <tex>n</tex> штук. Тогда, по [[Лемма Бёрнсайда и Теорема Пойа|лемме Бёрнсайда]], число орбит равняется <tex>\dfrac{n/}{p}=\operatorname{gcd}(n,i)</tex>, где <tex>p</tex> минимальное число такое, что <tex>ip</tex> делится на <tex>n</tex>, и число их раскрасок <tex>N_i=k^{\operatorname{gcd}(n,i)}</tex>. Сумма же инвариантных раскрасок для всех поворотов: <tex>S=\sum_sum\limits_{i=1}^{n}N_i=\sum_sum\limits_{i=1}^{n}k^{\operatorname{gcd}(n,i)}</tex>. В последней сумме <tex>\phivarphi(n)</tex> слагаемых<tex>(\varphi(n)</tex> {{---}} [[Функция Эйлера|функция Эйлера]]<tex>)</tex>, для которых <tex>\operatorname{gcd}(n,i)=1</tex>. Если же <tex>\operatorname{gcd}(n,i)=q</tex>, то <tex>\operatorname{gcd}\left(\dfrac{n/}{q},\dfrac{i/}{q}\right)=1</tex>. Чтобы определить количество таких <tex>i</tex>, меньших <tex>n</tex>, нужно перебрать числа вида <tex>i=lq,\,0\leq leqslant l\leq leqslant \dfrac{n/}{q}</tex> и проверять их на условие <tex>1=\operatorname{gcd}\left(\dfrac{n/}{q},\dfrac{i/}{q}\right)=\operatorname{gcd}\left(\dfrac{n/}{q},l\right)</tex>. Таких чисел, очевидно, <tex>\phivarphi\left(\dfrac{n/}{q}\right)</tex>(по определению <tex>\phivarphi(n)</tex>). Поэтому сумму можно заменить: <tex>S=\sum_sum\limits_{i=1}^{n}k^{\operatorname{gcd}(n,i)}=\sum_sum\limits_{q|n}\phivarphi\left(\dfrac{n/}{q}\right)k^q</tex>.

Тогда <tex>|C| =</tex> <tex dpi = "180"> \fracdfrac{1} {n}</tex><tex>\sum_sum\limits_{q|n}\phivarphi\left(\dfrac{n/}{q}\right)k^q</tex>.

[[Файл:axis_of_braclets.png|300px|thumb|right|слева Слева пример оси для нечётного случая, справа . Справа для чётного.]]Пусть теперь ожерелья считаются одинаковыми, если они не только переходят друг в друга поворотом, но и отражением относительно некоторой оси (ось может проходить через две противоположные бусинки или через две противоположные пустоты в чётном случае и через бусинку и пустоту напротив неё в нечётном случае). Такие ожерелья называются bracelets <ref>[https://en.wikipedia.org/wiki/Necklace_(combinatorics) braceletsNecklace (combinatorics)]</ref>.

* Поворот и отражение {{- --}} отражение.

* Отражение и поворот {{- --}} отражение.

* Отражение и отражение {{- --}} поворот.

<tex> |B| = </tex> <tex dpi = "140">\fracdfrac{1} {|G|}</tex><tex>\sum\limits_{k \in G}I(k)</tex>

<tex> |G| = 2n</tex>. Первые <tex>n</tex> операций {{--- }} повороты, и сумма количества их неподвижных точек, делённая на <tex>2n</tex>, принимает значение <tex>\fracdfrac{|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| = \fracdfrac{|C|}{2} + \fracdfrac{1}{2n}k^{\fracdfrac{n + 1}{2}}n = \fracdfrac{|C|}{2} + \fracdfrac{1}{2}k^{\fracdfrac{n + 1}{2}} </tex><tex dpi = "140"> = \fracdfrac{1} {2n}\sum_sum\limits_{q|n}\phivarphi\left(\dfrac{n/}{q}\right)k^q + \fracdfrac{1}{2}k^{\fracdfrac{n + 1}{2}} </tex>

<tex dpi = "140">|B| = \fracdfrac{|C|}{2} + \fracdfrac{1}{2n}\left(\fracdfrac{n}{2}k^{\frac{n}{2}} + \fracdfrac{n}{2}k^{\frac{n}{2} + 1}\right)</tex> <tex dpi = "140">= \fracdfrac{|C|}{2} + \fracdfrac{1}{4}k^{\frac{n}{2}}(k + 1) = \fracdfrac{1} {2n}\sum_sum\limits_{q|n}\phivarphi\left(\dfrac{n/}{q}\right)k^q + \fracdfrac{1}{4}k^{\frac{n}{2}}(k+1)</tex>

* [[Функция Эйлера]] == Примечания ==<references/> == Источники информации ==* [https://enru.wikipedia.org/wiki/Necklace_(combinatorics) Necklace (combinatorics)%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::Ожерелья]