Задача об ожерельях

Задача:

Требуется посчитать количество ожерелий из [math]n[/math] бусинок, каждая из которых может быть покрашена в один из [math] k [/math] цветов. При сравнении двух ожерелий их можно поворачивать, но не переворачивать (т.е. разрешается сделать циклический сдвиг).

Решение этой задачи опирается на лемму Бёрнсайда и теорему Пойа.

Алгоритм решения задачи про ожерелья

Пусть нам даны бусинки [math]k[/math] различных цветов, а ожерелье должно состоять из [math]n[/math] бусинок.

Для решения воспользуемся формулой из теоремы Пойа.

[math]|C| =[/math] [math] \dfrac{1} {|G|}[/math][math]\sum\limits_{l \in G} k^{P(l)}[/math]

По условию, перестановкой инвариантной данной будет любая перестановка, полученная из данной циклическим сдвигом. Очевидно, что для каждой перестановки длины [math]n[/math] существует ровно [math]n - 1[/math] инвариантная перестановка, то есть всего инвариантных перестановок в каждом классе [math]n[/math], теперь найдем [math]P(i)[/math]. Заметим, что в [math]i[/math]-ой перестановке на [math]l[/math]-ой позиции стоит элемент [math](i + l)\bmod n[/math]. Также, заметим, что элемент [math]a[/math] переходит в элемент [math]a + in[/math], где [math]i = 1, 2, \ldots k[/math]. Из этого следует, что длина цикла для [math]i[/math]-ой перестановки равна [math] \dfrac{\mathrm{lcm}(n, i)}{i} = \dfrac{n}{\mathrm{gcd}(i,n)}[/math], где [math]\mathrm{gcd}(i, n)[/math] — НОД[math](i, n)[/math], [math]\mathrm{lcm}(i, n)[/math] — НОК[math](i, n)[/math]. Откуда следует что:

[math]|C| =[/math] [math] \dfrac{1} {n}[/math][math]\sum\limits_{i = 1}^{n} k^{\mathrm{gcd}(i,n)}[/math].

где [math]|C|[/math] — кол-во различных ожерелий,которые можно составить из [math]n[/math] бусинок [math]k[/math] различных цветов.

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

Тогда [math]|C| =[/math] [math] \dfrac{1} {n}[/math][math]\sum\limits_{q|n}\varphi\left(\dfrac{n}{q}\right)k^q[/math]

Алгоритм решения задачи про ожерелья с отражениями

Слева пример оси для нечётного случая. Справа для чётного.

Пусть теперь ожерелья считаются одинаковыми, если они не только переходят друг в друга поворотом, но и отражением относительно некоторой оси (ось может проходить через две противоположные бусинки или через две противоположные пустоты в чётном случае и через бусинку и пустоту напротив неё в нечётном случае). Такие ожерелья называются bracelets . Будем пользоваться леммой Бёрнсайда. Разберём два случая.

Для начала покажем, что в качестве операций требуется рассматривать только повороты и отражения.

• Поворот и отражение — отражение.

Занумеруем наши бусинки по часовой стрелке. Поворот и отражение не меняют порядка (в каком-то направлении бусинки занумерованы по порядку). Нетрудно понять, что отражение меняет направление обхода наших бусинок и не меняет порядка. Если мы сначала сделаем поворот, а потом отразим относительно какой-нибудь оси, то мы то самое же можем получить и обыкновенным отражением относительно какой-то оси. Такая ось найдётся, потому что всегда можно выбрать ось, что поставит первую бусинку на своё изначальное место, поменяв направление обхода (если перебирать все оси подряд, начиная с оси, проходящей через нужную нам бусинку, то изначально она останется на своём месте, потом сместится на одно место, потом на два и.т.д.). Поэтому поворот и отражение не добавляет нам новой операции.

• Отражение и поворот — отражение.

Аналогичные рассуждения.

• Отражение и отражение — поворот.

Тут мы дважды меняем направление обхода, но не меняем порядка. Поэтому данная операция заменяется обычным поворотом.

Пусть число бусинок нечётное, тогда мы имеем [math]n[/math] осей, проходящих через каждую бусинку. Рассмотрим одну ось. Возьмём половину бусинок с одной стороны от оси и ту бусинку, через которую проходит данная ось. Мы можем окрасить их в произвольные цвета, а остальная половина по ним однозначно восстановится. Таким образом количество неподвижных точек для одной оси будет [math]k^{\frac{n + 1}{2}}[/math]. Операций в группе будет в два раза больше, чем было: [math]2n[/math] ([math]n[/math] сдвигов и [math]n[/math] отражений).

По Лемме Бёрнсайда: [math] |B| = [/math] [math]\dfrac{1} {|G|}[/math][math]\sum\limits_{k \in G}I(k)[/math]

[math] |G| = 2n[/math]. Первые [math]n[/math] операций — повороты, и сумма количества их неподвижных точек, делённая на [math]2n[/math], принимает значение [math]\dfrac{|C|} {2}[/math], где [math]|C|[/math] - количество ожерелий из [math]n[/math] бусинок [math]k[/math] различных цветов без отражений (задача выше) т.к. деление в задаче без отражений происходило на [math]n[/math], а здесь на [math]2n[/math]. Следующие [math]n[/math] операций — отражения. У каждой такой операции [math]k^{\frac{n + 1}{2}}[/math] неподвижных точек. Поэтому сумма получается [math]k^{\frac{n + 1}{2}}n[/math].

[math]|B| = \dfrac{|C|}{2} + \dfrac{1}{2n}k^{\dfrac{n + 1}{2}}n = \dfrac{|C|}{2} + \dfrac{1}{2}k^{\dfrac{n + 1}{2}} [/math][math] = \dfrac{1} {2n}\sum\limits_{q|n}\varphi\left(\dfrac{n}{q}\right)k^q + \dfrac{1}{2}k^{\dfrac{n + 1}{2}} [/math]

Разберём теперь чётный случай. Тут мы имеем [math]\frac{n}{2}[/math] осей, проходящих через пустоты между бусинками (ось можно провести через пустоту после каждой бусинки, но половина из них будет повторяться). В таких вот случаях можно выбрать по [math]\frac{n}{2}[/math] бусинок и дать им произвольные цвета. Остальная половина восстановится по ним. Таким образом для данных осей количество неподвижных точек будет [math]k^{\frac{n}{2}}[/math]. Ещё у нас есть [math]\frac{n}{2}[/math] осей, проходящих через бусинки. В данных случаях мы можем выбрать по [math]\frac{n}{2} + 1[/math] бусинок (бусинки на оси и все по одну какую-то сторону от неё). То есть будет [math]k^{\frac{n}{2} + 1}[/math] неподвижных точек. Операций также [math]2n[/math].

По Лемме Бёрнсайда:

[math]|B| = \dfrac{|C|}{2} + \dfrac{1}{2n}\left(\dfrac{n}{2}k^{\frac{n}{2}} + \dfrac{n}{2}k^{\frac{n}{2} + 1}\right)[/math] [math]= \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)[/math]

См. также

• Лемма Бёрнсайда и Теорема Пойа
• Функция Эйлера

Источники информации

• Википедия — Теорема Редфилда — Пойа, Задача о количестве ожерелий
• MAXimal::algo::Ожерелья