Coloring $n$ chain with $k$ colors

Chains are made from beads, each in one of $k$ colors. In each chain there is $n$ beads. We claim that two chains are the same if one can be made from second by cyclic rotation (mirror reflection is not allowed there). How many different chains can we get?

I want to use Polyi theorem. So let's deifine $$G = \left\{0,1,2,...,n-1 \right\} = \mathbb Z_n $$ where element $e \in G$ is treated as cyclic rotation with $e$ positions. Now I should write elements and cycles which are produces by them to cyclic index. \begin{array}{|c|c|c|c|} \hline elements& cycles\\ \hline 0 & x_1^n \\ \hline 1 & x_n^1 \\ \hline 2 & ? \\ \hline 3 & ? \\ \hline ... & ... \\ \hline n-3 & ? \\ \hline n-2 & ? \\ \hline n-1 & x_n^1 \\ \hline \end{array} I know what happened for elements $0,1,n-1$ but I completety don't know how to treat other elements due to the fact there is different approach in different combinations of $k$, $n$...

Solution 1:

I know Polyi Theorem in a slightly different form, so my apologies for the slightly different notation.

Let $G=\{0,1,2,...,n-1\}$ the cyclic group and let $X$ be the set of all colored arrangements of $n$ beads in $k$ colours. Note $\# X=k^{n}$. Now we need to calculate the cardinality of the fixed points of the elements of $G$: $\chi(g)=\#\{x\in X:gx=x\}$.

Let $d$ be a divisor of $n$, recall that the number of element of order $d$ in $G$ is $\varphi(d)$ where $\varphi$ is the Euler-$\varphi$ formula. Note that if $g$ is an element of order $d$ then $\chi(g)=k^{n/d}$.

Using Polyi's theorem we find that that the number of different coloured chains up cyclic rotation is given by: $$\#(G\verb?\?X)=\sum_{d,d|n}\varphi(d)k^{n/d}.$$