0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Would this be the case where reflections don't count either? $\endgroup$ – mathchai Dec 15 '15 at 4:16
  • $\begingroup$ Yes, I am including reflections (the same method works if you don't.) $\endgroup$ – David Hill Dec 15 '15 at 4:21
  • $\begingroup$ In the example do you mean $D_4$? $\endgroup$ – mathchai Dec 15 '15 at 4:57
  • $\begingroup$ There are multiple conventions. It is not uncommon to write $D_{2n}$ for the dihedral group of a regular $n$-gon. It has order $2n$. $\endgroup$ – David Hill Dec 15 '15 at 5:44

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.