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

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

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

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

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

Инвариантная перестановка — такая перестановка, которая по условию задачи не меняет сам объект, а только его представление.

Примером инвариантной перестановки в нашем случае является циклический сдвиг.

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

Неподвижной точкой [math]f[/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[/math] циклических сдвигов, теперь найдем [math]P(i)[/math]. Заметим, что в [math]i[/math]-ой перестановке на [math]l[/math]-ой позиции стоит элемент [math](i + l)\mod 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] различных цветов.

См. также

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