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

Определение:

Требуется посчитать количество ожерелий из [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 \in [1; k][/math]. Из этого следует, что длина цикла для [math]i[/math]-ой перестановки равна [math]lcm(n, i)/i = n/gcd(i,n)[/math]. Откуда следует что:

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

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

См. также

• Лемма Бёрнсайда и Теорема Пойа