Изменения
→Алгоритм решения задачи про ожерелья
<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 \in [1; k]</tex>. Из этого следует, что длина цикла для <tex>i</tex>-ой перестановки равна <tex>lcm(n, i)/i = n/gcd(i,n)</tex>. Откуда следует что:
<tex>|C | =</tex> <tex dpi = "180"> \frac{1} {n}</tex><tex>\sum\limits_{i = 1}^{n} k^{gcd(i,n)}</tex>.
где <tex>|C|</tex> - кол-во различных ожерелий,которые можно составить из <tex>n</tex> бусинок <tex>k</tex> различных цветов.
== См. также ==
