Число раскрасок $p$-угольника

[xmaister]

Я хочу посчитать число способов, которыми можно раскрасить $p$- угольник, $p$- просток в $1\le k<p$ различных цветов, так что раскраски считются одинаковыми, если одна получается из другой вращением.
Пользуюсь формулой Бернсайда. Надо сосчитать число орбит действия группы $G\cong\mathbb{Z}_p$ на множестве $X=\{\{(0,j_0),(1,j_1),\ldots ,(p-1,j_{p-1})\}|, 1\le j_i\le k\}$, так что $(g,(i,j))\mapsto ((i+g)\pmod{p},j)$. Пусть $k\in G$- произвольный. Как для него найти число неподвидных элементов множества $X$?

[xmaister]

Вроде посчитал. Число неподижных точек множеста при дейтсвии
элемента $e$-$k^p$. Пусть $g\ne e$. Тогда для произвольного $y\in X$ имеем $gy=y\Rightarrow j_{lg\pmod{p}}=j_0$ откуда для всякого $g\ne e$ число неподвижных точек в точности равно $k$. Тогда Бернсайд дставляет, что число различных раскрасок $\frac{k^p-p}{p}$, верно? А как это обощить на произвольное число сторон $n$?

[xmaister]

Там очепятка, должно быть $\frac{k^p+(p-1)k}{p}$

[ИСН]

Обобщение на произвольные пахнет суммой по всем делителям, с функцией Мёбиуса внутри.

[VAL]

xmaister в сообщении #628669 писал(а):

А как это обощить на произвольное число сторон $n$?

Посмотрите здесь.