Задача об ожерельях — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 35: Строка 35:
  
 
По Лемме Бёрнсайда:
 
По Лемме Бёрнсайда:
 +
<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">|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>  

Версия 18:47, 28 декабря 2013

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


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


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

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

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


[math]|C| =[/math] [math] \frac{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, ... k[/math]. Из этого следует, что длина цикла для [math]i[/math]-ой перестановки равна [math] \mathrm{lcm}(n, i)/i = n/\mathrm{gcd}(i,n)[/math]. Откуда следует что:

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


где [math]|C|[/math] - кол-во различных ожерелий,которые можно составить из [math]n[/math] бусинок [math]k[/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]\frac{1} {|G|}[/math][math]\sum\limits_{k \in G}I(k)[/math]

[math] |G| = 2n[/math]. Первые [math]n[/math] операций - повороты, и сумма количества их неподвижных точек, делённая на [math]2n[/math], принимает значение [math]\frac{|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| = \frac{|C|}{2} + \frac{1}{2n}k^{\frac{n + 1}{2}}n = \frac{|C|}{2} + \frac{1}{2}k^{\frac{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| = \frac{|C|}{2} + \frac{1}{2n}(\frac{n}{2}k^{\frac{n}{2}} + \frac{n}{2}k^{\frac{n}{2} + 1}) = \frac{|C|}{2} + \frac{1}{4}k^{\frac{n}{2}}(k + 1)[/math]

См. также