Изменения

Если раскраски ожерелья одинаковые, то они принадлежат одной [[Орбита|орбите]], т.е. одна получается из другой некоторым преобразованием симметрии. Неподвижные точки поворота есть только у тождественного поворота и их <tex>n</tex> штук. Тогда, по [[Лемма Бёрнсайда и Теорема Пойа|лемме Бёрнсайда]], число орбит равняется <tex>n/p=\operatorname{gcd}(n,ki)</tex>, где <tex>p</tex> минимальное число такое, что <tex>ip</tex> делится на <tex>n</tex>, и число их раскрасок <tex>N_i=k^{\operatorname{gcd}(n,i)}</tex>. Сумма же инвариантных раскрасок для всех поворотов: <tex>S=\sum_{i=1}^{n}N_i=\sum_{i=1}^{n}k^{\operatorname{gcd}(n,i)}</tex>. В последней сумме <tex>\phi(n)</tex> слагаемых, для которых <tex>\operatorname{gcd}(n,i)=1</tex>. Если же <tex>\operatorname{gcd}(n,i)=q</tex>, то <tex>\operatorname{gcd}(n/q,i/q)=1</tex>. Чтобы определить количество таких i, меньших n, нужно перебрать числа вида <tex>i=lq,\,0\leq l\leq n/q</tex> и проверять их на условие <tex>1=\operatorname{gcd}(n/q,i/q)=\operatorname{gcd}(n/q,l)</tex>. Таких чисел, очевидно, <tex>\phi(n/q)</tex>(по определению <tex>\phi(n)</tex>). Поэтому сумму можно заменить: <tex>S=\sum_{i=1}^{n}k^{\operatorname{gcd}(n,i)}=\sum_{q|n}\phi(n/q)k^q</tex>.