Изменения
Нет описания правки
где <tex>|C|</tex> - кол-во различных ожерелий,которые можно составить из <tex>n</tex> бусинок <tex>k</tex> различных цветов.
Если раскраски ожерелья одинаковые, то они принадлежат одной орбите, т.е. одна получается из другой некоторым преобразованием симметрии. Тогда, по лемме Бернсайда, число орбит равняется <tex>n/p=\operatorname{gcd}(n,k)</tex>, где <tex>p</tex> минимальное число такое, что <tex>ip</tex> делится на <tex>n</tex> и число их раскрасок <tex>N_i=k^{\operatorname{gcd}(n,i)}</tex>. Сумма же инвариантных раскрасок для всех поворотов: <tex>S=\sum_{i=0}^{n-1}N_k=\sum_{i=0}^{n-1}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=0}^{n-1}k^{\operatorname{gcd}(n,i)}=\sum_{q|n}\phi(n/q)k^q</tex>.
