# 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$$...

• The following MSE link may be helpful here. – Marko Riedel Jun 4 at 16:20

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}.$$