[Math] Expression of the number of distinct necklaces with $m$ beads of $n$ different colors.(rotations don’t count)

abstract-algebracombinatoricsgroup-theorypermutations

Suppose I want to form an $m$-bead necklace such that each bead can have $n$ different colors. Necklaces which differ by a rotation are considered the same and beads of the same color are indistinguishable. Can we find an expression of the number of distinct necklaces then? I'm thinking about using Burnside's lemma but don't know how to find $\sum_{g\in G} |fix(g)|$.

Best Answer

You are correct, you want to use Burnside's lemma:

$$\mbox{# of Orbits}=\frac{1}{|G|}\sum_{g\in G}|fix(g)|.$$

You have an action of $G=D_{2m}$ on the set $X$ of $n$-colored necklaces with $m$ beads, and two such necklaces are the same if they are in the same orbit under this action. Therefore, counting the number of orbits counts the number of necklaces.

Let's set up some notation. We can regard a necklace as a regular $n$-gon with vertices numbered $\{1,\ldots,m\}$. Then, $G$ act on the vertices in the natural way. This corresponds to an embedding $G\hookrightarrow S_m$. Identifying an element $g\in G$ with its image in $S_m$, let $\psi(g)$ denote the number of disjoint cycles in the cycle decomposition of $g$.

Let $C$ be a set of $n$ colors (i.e. $|C|=n$). Then $G$ acts on $X=C^m$ by $$g.(c_1,\ldots,c_m)=(c_{g.1},\ldots,c_{g.m}).$$

Lemma: For the action of $G$ on $X$, we have $|fix(g)|=n^{\psi(g)}$.

proof: Since, for all $k$, $g^k.(c_1,\ldots,c_m)=(c_{g^k.1},\ldots,c_{g^k.m})$ we see that $(c_1,\ldots,c_m)$ is in $fix(g)$ if, and only if $c_i=c_{g^k.i}$ for all $i$ and $k$. This just says that $(c_1,\ldots,c_m)\in fix(g)$ if, and only if the coloring is constant on the cycles of $g$. There are $n$ choices to color each cycle, leading to $n^{\psi(g)}$ total colorings that are fixed by $g$.

Example: Suppose $m=4$ and $n=3$. The element of $D_8$ and their cycles types are chosen as follows: $$ \begin{array}{llll} 1=(1)(2)(3)(4)&r=(1234) &r^2=(13)(24)&r^3=(4321)\\ j=(24)(1)(3)&rj=(12)(34)&r^2j=(13)(2)(4)&r^3j=(14)(23) \end{array} $$ The corresponding orders of $fix(g)$ are given by $$ \begin{array}{llll} n^4&n&n^2&n\\ n^3&n^2&n^3&n^2 \end{array} $$ Therefore, the number of necklaces with $n$ colors is $$\frac{1}{8}(n^4+2n^3+3n^2+2n).$$ Substituting $n=3$ yields $21$ distinct necklaces.