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

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
Требуется посчитать количество ожерелий из [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] различных цветов.


См. также