10
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ The following MSE link may be helpful here. $\endgroup$ – Marko Riedel Jun 4 at 16:20
2
+100
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.