I'm a high-school student and I stumbled across a YouTube video explaining how Rubik's cubes work. A Rubik's cube has 6 colors, one for each side, but I started thinking about ways to $n$-color the cube and other $2n$-polyhedra.

While researching it I came across group theory, which led me to learn about Burnside's lemma (this is a really deep rabbit hole!). As I understand it, the way that it works is that you first find the cycle index for the group you want to consider, which in our case lets us count all the ways you can permute the faces of the polyhedron. Then it's a straightforward substitution with $n$ = the number of colors to consider.

For instance, the cycle index of the cube tells us that if we have n colors, then there are

$\frac{1}{3}n^2 + \frac{1}{2}n^3 + \frac{1}{8}n^4 + \frac{1}{24}n^6$

ways to color the cube. So there are $1, 10, 57, 240, ...$ ways to color a cube with $n = 1, 2, 3, 4, ...$ colors.

I think I understand how to find the cycle index for a few of the 2n-polyhedra, so I know how many ways there are to color all the sides using up to $n$ colors. (I don't know how to find the cycle index for every 2n-polyhedron without considering the graphs one at a time, though; is there a generating function for that?)

However, what I'd like to know is how to tell how many ways there are to color a $2n$-polyhedron using $n$ colors, where each color is used exactly twice.

Any hints? Where I'm at right now is that it seems like the cycle index would still figure prominently, but now some of the enumerations aren't considered -- basically, every time there is a coloring that uses a color in a frequency other than twice, we want to throw it away. But I can't see how to count in which of the cases a color is used in a frequency other than twice.

  • $\begingroup$ I wrote a tutorial about using Burnside's lemma that you might find helpful, although it doesn't address your specific question; this answer does address your specific question, since it talks about using Burnside's lemma to count the number of colorings of a cube with exactly 2 faces each of three colors. $\endgroup$ – MJD Jun 6 '13 at 14:48
  • $\begingroup$ @MJD Thanks! It looks like you have to consider each symmetry "flavor" in the cycle index and think about whether the set of generated orbits can be assigned to by $k$ different colors (where k is 2 in this case). Is there a way to generalize this work to a closed-form solution, so that one doesn't have to manually compute it each time? $\endgroup$ – James Faulcon Jun 6 '13 at 15:27
  • $\begingroup$ Although I would like to know that, I don't. That's why I posted a comment instead of an answer. I hope someone else has something more useful to say. $\endgroup$ – MJD Jun 6 '13 at 15:28
  • $\begingroup$ It depends on what you mean by 2n-polyhedron. A cube is a very special type of polyhedron -- it is a Platonic solid, of which there are only five. The answer to your question will vary depending on the types and number of symmetries that are present in your particular 2n-polyhedra. $\endgroup$ – user105438 Nov 4 '13 at 22:30
  • $\begingroup$ It's worth noting, though, that there are only a few finite rotation groups in R^3. You have the Z_n family, the D_n family, and then the three outliers A_4, A_5, and S_4. $\endgroup$ – user105438 Nov 4 '13 at 22:41

This question has a definite answer, which is to use the Polya Enumeration Theorem, which is more powerful than Burnside and includes it as a special case. It will produce a multivariate generating function for all distributions of colors, from which you may extract the desired coefficient for a given configuration. You compute the cycle index of the face permutation group $G$ of the polyhedron and evaluate it using the substitution $$a_k = X_1^k + X_2^k + \cdots + X_n^k$$ if you have $n$ colors. Then you extract the coefficient for your particular configuration, which is written like this: $$[X_1^2 X_2^2 \cdots X_n^2] Z(G)(X_1+X_2+\cdots+X_n).$$

Here are two simple examples where we restrict ourselves to rigid motions (no reflections). Suppose we have a tetrahedron whose faces we want to color. The cycle index of $G$ for this case contains the identity, which contributes $$a_1^4.$$ Then there are rotations about axes passing through the middle of a face and the opposing vertex (four such axes), which fix that face and contribute $$4\times 2\times a_1 a_3.$$ Finally there are three flips by 180 degrees about an axis passing through the midpoints of two vertex-disjoint edges (three such axes), which contribute $$3\times a_2^2.$$ This gives the cycle index $$Z(G) = \frac{1}{12} (a_1^4 + 8 a_1 a_3 + 3 a_2^2).$$ We can recover Burnside from this via $$Z(G)(X_1+X_2+\cdots+X_n)_{X_1=X_2=\cdots=X_n=1}$$ which gives the formula $$\frac{1}{12} (n^4 + 8 n^2 + 3 n^2) = \frac{1}{12} n^4 + \frac{11}{12} n^2.$$ for colorings of the tetrahedron with at most $n$ colors. This sequence is documented as OEIS A006008.

Now to answer your question, suppose we have three colors $R$, $G$ and $B$ and we want the number of colorings where two colors are used twice. This is where the substituted cycle index comes into play. Making the substitution as described above we have $$Z(G)(R+B+G)\\ = 1/12\, \left( R+G+B \right) ^{4}+2/3\, \left( R+G+B \right) \left( {R}^{3 }+{G}^{3}+{B}^{3} \right) +1/4\, \left( {R}^{2}+{G}^{2}+{B}^{2} \right) ^{ 2}$$ which expands to $${B}^{4}+{B}^{3}G+{B}^{3}R+{B}^{2}{G}^{2}+{B}^{2}GR+{B}^{2}{R}^{2}+B{G}^{3} +B{G}^{2}R\\+BG{R}^{2}+B{R}^{3}+{G}^{4}+{G}^{3}R+{G}^{2}{R}^{2}+G{R}^{3}+{R} ^{4}.$$ Extracting coefficients we see that $$[R^2 G^2]Z(G)(R+G+B)+[R^2 B^2]Z(G)(R+G+B)+[G^2 B^2]Z(G)(R+G+B) = 3,$$ so there are three colorings up to rotation of the faces of the tetrahedron with three available colors using two colors twice.

As a second example consider painting the faces of a cube with three colors. We need another cycle index call it $Z(H)$, the one of the face permutation group of the cube, which is actually a fairly standard computation. There is the identity, which contributes $$a_1^6.$$ There are rotations about an axis passing through opposite faces (three such axes) which fix those faces, giving $$3\times (2 a_1^2 a_4 + a_1^2 a_2^2).$$ There are rotations about axes passing through opposite vertices (four such axes), giving $$4\times 2 \times a_3^2.$$ Finally there are rotations about axes passing through the midpoints of pairs of opposite edges (six such pairs), which contribute $$6\times a_2^3.$$ This gives the cycle index $$Z(H) = \frac{1}{24} (a_1^6 + 6 a_1^2 a_4 + 3 a_1^2 a_2^2 + 8 a_3^2 + 6 a_2^3).$$ We recover Burnside from this as above, getting $$\frac{1}{24} (n^6 + 6 n^3 + 3 n^4 + 8 n^2 + 6 n^3) = \frac{1}{24} (n^6 + 3 n^4 + 12 n^3 + 8 n^2) \\= \frac{1}{24} n^6 + \frac{1}{8} n^4 + \frac{1}{2} n^3 + \frac{1}{3} n^2.$$ This is sequence is OEIS A047780. Now to get the colorings using each color twice we compute the substituted cycle index $$Z(H)(R+G+B)= 1/24\, \left( R+G+B \right) ^{6}+1/4\, \left( R+G+B \right) ^{2} \left( {R }^{4}+{G}^{4}+{B}^{4} \right) \\+1/8\, \left( R+G+B \right) ^{2} \left( {R}^ {2}+{G}^{2}+{B}^{2} \right) ^{2}+1/3\, \left( {R}^{3}+{G}^{3}+{B}^{3} \right) ^{2}+1/4\, \left( {R}^{2}+{G}^{2}+{B}^{2} \right) ^{3}$$ which expands to $${B}^{6}+{B}^{5}G+{B}^{5}R+2\,{B}^{4}{G}^{2}+2\,{B}^{4}GR+2\,{B}^{4}{R}^{2} +2\,{B}^{3}{G}^{3}\\+3\,{B}^{3}{G}^{2}R+3\,{B}^{3}G{R}^{2}+2\,{B}^{3}{R}^{3} +2\,{B}^{2}{G}^{4}+3\,{B}^{2}{G}^{3}R+6\,{B}^{2}{G}^{2}{R}^{2}\\+3\,{B}^{2}G {R}^{3}+2\,{B}^{2}{R}^{4}+B{G}^{5}+2\,B{G}^{4}R+3\,B{G}^{3}{R}^{2}+3\,B{G} ^{2}{R}^{3}+2\,BG{R}^{4}\\+B{R}^{5}+{G}^{6}+{G}^{5}R+2\,{G}^{4}{R}^{2}+2\,{G }^{3}{R}^{3}+2\,{G}^{2}{R}^{4}+G{R}^{5}+{R}^{6}.$$ Extracting coefficients we now see that $$[R^2 G^2 B^2]Z(H)(R+G+B) = 6,$$ so there are six colorings using each of the three colors exactly twice.

The following MSE link points to a chain of similar computations.

  • $\begingroup$ It took me a long time to get through all this (I'm coming back to this question about 1.3 years later!), but I think I finally understood all of it. Thanks for your answer! $\endgroup$ – James Faulcon Apr 26 '15 at 18:07

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.