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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 4: Строка 4:
  
  
Решение этой задачи опирается на [[Лемма Бёрнсайда и Теорема Пойа|Лемму Бёрнсайда и Теорему Пойа]].
+
Решение этой задачи опирается на [[Лемма Бёрнсайда и Теорема Пойа|лемму Бёрнсайда и теорему Пойа]].
  
  
Строка 25: Строка 25:
  
  
 +
== Алгоритм решения задачи про ожерелья с отражениями==
  
Пусть теперь ожерелья считаются одинаковыми, если они не только переходят друг в друга поворотом, но и отражением относительно некоторой оси.
+
Пусть теперь ожерелья считаются одинаковыми, если они не только переходят друг в друга поворотом, но и отражением относительно некоторой оси. Такие ожерелья называются [https://en.wikipedia.org/wiki/Necklace_(combinatorics) bracelets].
Будем пользоваться [[Лемма Бёрнсайда и Теорема Пойа|Леммой Бёрнсайда]].
+
Будем пользоваться [[Лемма Бёрнсайда и Теорема Пойа|леммой Бёрнсайда]].
 
Разберём два случая.
 
Разберём два случая.
  
Пусть число бусинок нечётное, тогда мы имеем <tex>n</tex> осей, проходящих через каждую бусинку. Рассмотрим одну ось. Возьмём половину бусинок с одной стороны от оси и ту бусинку, через которую проходит данная ось. Мы можем окрасить их в произвольные цвета, а остальная половина по ним однозначна восстановится. Таким образом количество неподвижных точек для одной оси будет <tex>k^{\frac{n + 1}{2}}</tex>.  
+
Пусть число бусинок нечётное, тогда мы имеем <tex>n</tex> осей, проходящих через каждую бусинку. Рассмотрим одну ось. Возьмём половину бусинок с одной стороны от оси и ту бусинку, через которую проходит данная ось. Мы можем окрасить их в произвольные цвета, а остальная половина по ним однозначно восстановится. Таким образом количество неподвижных точек для одной оси будет <tex>k^{\frac{n + 1}{2}}</tex>.  
 
Операций в группе будет в два раза больше, чем было: <tex>2n</tex> (<tex>n</tex> сдвигов и <tex>n</tex> отражений).
 
Операций в группе будет в два раза больше, чем было: <tex>2n</tex> (<tex>n</tex> сдвигов и <tex>n</tex> отражений).
  
Строка 48: Строка 49:
 
== См. также ==
 
== См. также ==
 
* [[Лемма Бёрнсайда и Теорема Пойа]]
 
* [[Лемма Бёрнсайда и Теорема Пойа]]
 
+
* [https://en.wikipedia.org/wiki/Necklace_(combinatorics) Necklace (combinatorics)]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Комбинаторика]]
 
[[Категория: Комбинаторика]]

Версия 15:54, 24 декабря 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| = \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]

См. также