Burnside Lemma Necklace Problem

Question

I am trying to solve the following problem:

How many necklaces can we make that use $4$ red stones, $5$ blue stones and $3$ green stones, such that the necklaces are in the shape of a regular dodecagon.

I know I need to use the Cauchy-Frobenius (or Burnside) Lemma to count the "Fixes" of all the rotations and flips of $D_{12}$, which we can describe as:

$$D_{12}=\langle x,y\text{ }\Big|\text{ }x^2=e,y^{12}=e, xyxy=e\rangle$$

I have already calculated the fixes for $e$ (which is $\frac{12!}{5!4!3!}$), and for powers of $y^i$, where $i=1,5,7,11$. For $i=1$, I noted that we would eventually reach the conclusion that all of the stones must be the same, which is obviously false. For $i=5,7,11$, I said that since their $gcd(i,12)=1$, we could eventually find $n$ such that $(y^i)^n=y$, which we have shown has a Fix of 0.

These solutions have been rather intuitive, and not super mathematically rigorous. I have an intuition that the remaining powers of $y$ will also have fixes of $0$ (after some testing with specific examples), but I'm not entirely certain how to prove it. I was thinking of using the fact that we can describe $D_{12}$ as the permutations of the numbers $1,2,...,12$, and that the orbits of these remaining $y^i$ do not have size $5$ or $3$, and thus we cannot have a fix for these $y^i$. However, I'm not certain if the correlation between these two things is as strong as I'm hoping it is.

If it is the case that the orbits formed by a permutation of $D_{12}$ do tell us about the Fix in this way, then I feel confident that I can figure out the Fixes for $xy^i$. However, if this is not the case, then a suggestion as to where to start would be sincerely appreciated. Cheers.

Answer 1

Yes, it is a very good idea to label the vertices of the dodecagon from $1$ to $12$ and then to study the permutations induced on the set $\{1,\ldots,12\}$ by the symmetries in $D_{12}$ - these are extremely related.

More specifically, you want to think about the orbits of these points under the symmetry. Presumably, to see that a pattern symmetric with the rotation $y$ would only have one color, you first reason that vertices $1$ and $2$ must be the same color because $1$ is moved to $2$ by $y$. Then $2$ and $3$ must have the same color too - and so on.

If you write the permutation induced by $y$ in disjoint cycle notation, you get $$y \rightarrow (1\,2\,3\,4\,5\,6\,7\,8\,9\,10\,11\,12)$$ where, in case this notation is unfamiliar, each number maps to the one to the right of it and the last term maps to the first. Everything in a cycle must be the same color. If we want to study the fix of $y^2$, we can write that in permutation notation: $$y^2\rightarrow (1\,3\,5\,7\,9\,11)(2\,4\,6\,8\,10\,12)$$ where we have two orbits - each of which must be the same color. However, there is still clearly no way to assign colors to orbits to satisfy the counts desired. In general, you can find that, as you suspect, the elements $y^n$ for $n\neq 0$ will not have a fix because it will not be possible to color the orbits in any way to get the desired numbers - you can prove, for instance, that $y^n$ has $\gcd(n,12)$ orbits of equal size. This serves as a generalization of what you already have.

Then, for the flips, you will find two possible configurations of orbits: six flips consist of $6$ orbits of size $2$ and the other six consist of $5$ orbits of size $2$ and $2$ orbits of size $1$. For instance, two possible flips are the flip along the $1$ to $7$ axis given as $$(1)(2\,12)(3\,11)(4\,10)(5\,9)(6\,8)(7)$$ and the one which is along the perpendicular bisector of the edge from $1$ to $2$ given as $$(1\,2)(3\,12)(4\,11)(5\,10)(6\,9)(7\,8).$$ You can note that, in the latter case, there is no way to color the orbits appropriately, since the orbits all have even size. In the former case, however, you will find that you can color the orbits - which means that there is some fix of these symmetries.

To find the size of that fix, you can just note that you must first color one of the orbits of size $1$ blue and the other green (giving $2$ choices) and then, of the remaining orbits of size $2$, color $2$ red, $2$ blue, and $1$ green. This lets you extend your reasoning to find all the fixes for this problem and thus to compute the number of necklaces possible.

Answer 2

Given that we have dihedral symmetry we suppose we are working with bracelets (naming convention by OEIS). This requires the cycle index $Z(D_{12})$ of the dihedral group $D_{12}.$ We have for the cyclic group that

$$Z(C_{12}) = \sum_{d|12} \varphi(d) a_d^{12/d} = \frac{1}{12} (a_1^{12} + a_2^6 + 2 a_3^4 + 2 a_4^3 + 2 a_6^2 + 4 a_{12}).$$

We get twelve more permutations corresponding to flips about an axis passing through opposite slots or opposite edges, for a result of

$$Z(D_{12}) = \frac{1}{24} (a_1^{12} + a_2^6 + 2 a_3^4 + 2 a_4^3 + 2 a_6^2 + 4 a_{12}) + \frac{1}{24} ( 6 a_1^2 a_2^5 + 6 a_2^6).$$

By the Polya Enumeration Theorem (PET) we are interested in the quantity

$$[R^4 G^3 B^5] Z(D_{12}; R+G+B).$$

Working through the rotational terms we find

• $[R^4 G^3 B^5] (R+G+B)^{12} = {12\choose 4,3,5}.$

The terms other than the first produce second, third, fourth, sixth and twelfth powers of $R,G$ and $B$ simultaneously and hence can never yield $R^4 G^3 B^5$, making for a zero contribution.

We get from the reflections

• $[R^4 G^3 B^5] 6 (R+G+B)^2 (R^2+G^2+B^2)^5 \\ = [R^4 G^2 B^4] 12 (R^2+G^2+B^2)^5 = [R^2 G^1 B^2] 12 (R+G+B)^5 \\ = 12 \times {5\choose 2,1,2},$
• $[R^4 G^3 B^5] 6 (R^2+G^2+B^2)^{6} = 0.$

Collecting everything we find for our result that it is

$$\frac{1}{24} \left({12\choose 4,3,5}+ 12 {5\choose 2,1,2}\right).$$

which yields

$$\bbox[5px,border:2px solid #00A000]{1170.}$$