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

2013-12-22T00:10:00Z

78.25.121.156:

{{Определение
|definition=
Требуется посчитать количество ожерелий из <tex>n</tex> бусинок, каждая из которых может быть покрашена в один из <tex> k </tex> цветов. При сравнении двух ожерелий их можно поворачивать, но не переворачивать (т.е. разрешается сделать циклический сдвиг).}}

Решение этой задачи опирается на [[Лемма Бёрнсайда и Теорема Пойа|Лемму Бёрнсайда и Теорему Пойа]].

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

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

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

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

<tex>|C| =</tex> <tex dpi = "180"> \frac{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>k^{\frac{n + 1}{2}}</tex>.
Операций в группе будет в два раза больше, чем было: <tex>2n</tex> (<tex>n</tex> сдвигов и <tex>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>\frac{n}{2}</tex> осей, проходящих через пустоты между бусинками (ось можно провести через пустоту после каждой бусинки, но половина из них будет повторяться). В таких вот случаях можно выбрать по <tex>\frac{n}{2}</tex> бусинок и дать им произвольные цвета. Остальная половина восстановится по ним. Таким образом для данных осей количество неподвижных точек будет <tex>k^{\frac{n}{2}}</tex>.
Ещё у нас есть <tex>\frac{n}{2}</tex> осей, проходящих через бусинки. В данных случаях мы можем выбрать по <tex>\frac{n}{2} + 1</tex> бусинок (бусинки на оси и все по одну какую-то сторону от неё). То есть будет <tex>k^{\frac{n}{2} + 1}</tex> неподвижных точек. Операций также <tex>2n</tex>.

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

<tex dpi = "140">|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)</tex>

== См. также ==
* [[Лемма Бёрнсайда и Теорема Пойа]]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Викиконспекты - Вклад участника [ru]

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