Coloring a cube with 4 colors

Question

There are some topics on this forum related to my question. Most of them use Burnsides Lemma. I don't know this lemma and I don't know whether it is applicable to my problem. Can someone explain the lemma to me when it is needed to solve my problem?

The problem states that we need to color the sides of a cube with 4 colors. We want to know how many different cubes we can get. I programmed this problem and my answer is 84. It seems quite unlikely that there are so few possibilities. Can someone calculate the answer using mathematical reasoning?

Answer 1

Your number is indeed too low. One can show that you are wrong without actually determining the exact number of different cubes. If you want the exact number, this is easily done using Burnside's Lemma as others have mentioned.

However, it turns out that the number $84$ counts something which is easily seen to be less than the number of cubes, and so I suspect that this is what your program actually counted. Hence, this answer may be of use to you.

We can undercount the number of cubes by just counting according to the distribution of colours used. A distribution is just a non-decreasing sequence of at most 4 integers that sum to 6.

There are

4 of type (6)

6 of type (3,3)

12 of type (1,5)

12 of type (2,4)

4 of type (2,2,2)

12 of type (1,1,4)

24 of type (1,2,3)

4 of type (1,1,1,3)

6 of type (1,1,2,2)

If you add that up you magically get the number $84$.

To see that $84$ actually undercounts cubes, note that there two cubes with two red faces and four blue faces, depending if the red faces are adjacent or not. Thus, there are at least 85 cubes.

Answer 2

[I copied the first portion of this answer, describing the symmetries of the cube, from my answer to a related question here.]

First you enumerate the elements of the symmetry group of the cube. There are 24 of these, falling into five different classes:

1. 6 elements that are rotations of $\pm90^\circ$ around axes through face centers
2. 3 elements that are rotations of $180^\circ$ around axes through face centers
3. 8 elements that are rotations of $\pm120^\circ$ around axes through opposite vertices
4. 6 elements that are rotations of $180^\circ$ around axes through the midpoints of opposite edges
5. 1 identity element

Our job is to count how many ways there are to assign colors to the faces that are left unchanged by each of the 24 symmetries. The average of these 24 counts is the answer we want.

Each of these 5 sorts of symmetries divides the faces of the cube into "orbits", which are equivalence classes of faces which can be mapped to one another by just that symmetry. All the faces in a single orbit must me painted the same color.

For symmetries of sort 1, there are three orbits, consisting of 1, 1, and 4 faces respectively: say the axis goes through the top and bottom faces. Then the top face is one orbit, the bottom face is another orbit, and the four faces around the middle are the third orbit. The faces in each orbit must be painted the same color, and there are three orbits, so there are $4^3 = 64$ ways to paint the faces that are left unchanged by a $\pm90^\circ$ rotation around a face-centered axis.

Similarly, symmetries of sort 2 divide the faces into 4 orbits, so there are $4^4 = 256$ colorings left fixed by these 3 symmetries.

Symmetries of sort 3 divide the cube into 2 orbits, so there are $4^2 = 16$ colorings left fixed by these symmetries.

Symmetries of sort 4 divide the cube into 3 orbits, so there are $4^3 = 64$ colorings left fixed by these symmetries.

Finally, all $4^6$ possible colorings are left fixed by the identity symmetry.

We then average the number of colorings left unchanged by each symmetry. This gives us

$$\begin{align} \frac{1}{24}\left(6\cdot4^3 + 3\cdot 4^4 + 8\cdot 4^2 + 6\cdot 4^3 + 4^6\right) & = \\ \frac1{24}(384 + 768 + 128 + 384 + 4096) & = \frac{5760}{24} \\& = {\Large \color{darkred}{240}}. \end{align}$$

By the Cauchy–Frobenius–Redfield–Pólya–Burnside counting lemma, this average is the number of ways of coloring the faces of the cube with four colors.

Answer 3

This can be done using Polya's theorem, but we need the cycle index of the face permutation group $F$ (once we have this index we could also use Burnside).

We proceed to enumerate the permutations of this group. There is the identity, which contributes $$a_1^6.$$ There are three rotations for each pair of opposite faces that fix those faces (rotate about the axis passing through the center of the two faces). They contribute $$3\times (2 a_1^2 a_4 + a_1^2 a_2^2).$$ There are rotations about an axis passing through opposite vertices, of which there are four pairs, giving $$4\times 2 a_3^2.$$ Finally we may rotate about an axis passing through the centers of opposite edges and there are six of these, giving $$6\times a_2^3.$$

It follows that the cycle index of $F$ is given by $$Z(F) = \frac{1}{24} \left(a_1^6 + 6a_1^2a_4 + 3a_1^2a_2^2 + 8a_3^2 + 6a_2^3\right).$$

With four colors we have $$Z(F)(W+X+Y+Z) \\= 1/24\, \left( W+X+Y+Z \right) ^{6}\\+1/4\, \left( W+X+Y+Z \right) ^{2} \left( {W}^ {4}+{X}^{4}+{Y}^{4}+{Z}^{4} \right) \\+1/8\, \left( W+X+Y+Z \right) ^{2} \left( {W }^{2}+{X}^{2}+{Y}^{2}+{Z}^{2} \right) ^{2}\\+1/3\, \left( {W}^{3}+{X}^{3}+{Y}^{3}+ {Z}^{3} \right) ^{2}\\+1/4\, \left( {W}^{2}+{X}^{2}+{Y}^{2}+{Z}^{2} \right) ^{3}.$$

This ordinary generating function provides more information than Burnside alone, namely through its coeffcients. We have, for example, that $$[WXYZ^3] Z(F)(W+X+Y+Z) = 5,$$ which says that there are five colorings where colors $X, Y$ and $Z$ ocurr exactly once and color $Z$ three times. Obviously we also have $$[WXY^3Z] Z(F)(W+X+Y+Z) = 5,$$ by symmetry. Furthermore, we have $$[W^2X^2Y^2] Z(F)(W+X+Y+Z) = 6,$$ hence there are six cubes with colors $W,X,Y$ each ocurring twice. It is a very useful exercise to pick out one of these coefficients and verify its value using pen and paper.

Evaluating the substituted cycle index at $W=1, X=1, Y=1, Z=1$ we get $$Z(F)(W+X+Y+Z)_{W=1, X=1, Y=1, Z=1} = 240.$$ The sequence of colorings when there are $N$ colors is as follows: $$1, 10, 57, 240, 800, 2226, 5390, 11712, 23355, 43450, \ldots.$$ This is sequence A047780 from the OEIS.

Another related cycle index is the cycle index of the permutation group $G$ obtained when we add reflections to the admissible transformations of the cube. This yields the full symmetry group of the regular octrahedron. $$ Z(G) = 1/48\,{a_{{1}}}^{6}+1/16\,{a_{{1}}}^{4}a_{{2}}+3/16\,{a_{{1}}}^{2}{a_{{2}}}^{2}+ 1/8\,{a_{{1}}}^{2}a_{{4}}\\+{\frac {7}{48}}\,{a_{{2}}}^{3}+1/6\,{a_{{3}}}^{2}+1/6 \,a_{{6}}+1/8\,a_{{4}}a_{{2}}.$$ The corresponding sequence is $$1, 10, 56, 220, 680, 1771, 4060, 8436, 16215, 29260,\ldots$$ which is A198833 from the OEIS. This cycle index can be computed algorithmically without the need to classify the different types of symmetries. It suffices to encode the adjacencies of the faces and select those permutations of the symmetric group that turn out to be automorphisms. This is the code. The reader may want to attempt the classification without a CAS. As these groups contain more and more elements an algorithm can be useful.

with(numtheory);
with(group):
with(combinat):


pet_autom2cycles :=
proc(src, aut)
        local numa, numsubs;
        local marks, pos, cycs, cpos, clen;

        numsubs := [seq(src[k]=k, k=1..nops(src))];
        numa := subs(numsubs, aut);

        marks := [seq(true, pos=1..nops(aut))];

        cycs := []; pos := 1;

        while pos <= nops(aut) do
              if marks[pos] then
                 clen := 0; cpos := pos;

                 while marks[cpos] do
                       marks[cpos] := false;
                       cpos := numa[cpos];
                       clen := clen+1;
                 od;

                 cycs := [op(cycs), clen];
              fi;

              pos := pos+1;
        od;

        return mul(a[cycs[k]], k=1..nops(cycs));
end;


f := {{1,2},{1,3},{1,4},{1,5},
     {2,3},{2,5},{2,6},
     {3,4},{3,6},
     {4,5},{4,6},
     {5,6}};

cube_cind :=
proc()
         option remember;
         local ff, p, res, count, term;

         count := 0; res := 0;

         for p in permute(6) do
             ff := subs([seq(k=p[k], k=1..6)], f);
             if f = ff then
                 count := count+1;
                 term := pet_autom2cycles([seq(k,k=1..6)], p);
                 res := res+ term;
             fi;
         od;

         print(count);

         res/count;
end;

pet_varinto_cind :=
proc(poly, ind)
           local subs1, subs2, polyvars, indvars, v, pot, res;

           res := ind;

           polyvars := indets(poly);
           indvars := indets(ind);

           for v in indvars do
               pot := op(1, v);

               subs1 :=
               [seq(polyvars[k]=polyvars[k]^pot,
               k=1..nops(polyvars))];

               subs2 := [v=subs(subs1, poly)];

               res := subs(subs2, res);
           od;

           res;
end;

v :=
proc(n)
        option remember;
        local p, k, gf;

        p := add(cat(q, k), k=1..n);
        gf := expand(pet_varinto_cind(p, cube_cind()));

        subs({seq(cat(q, k)=1, k=1..n)}, gf);
end;

Note that we can also compute the cycle index of $F$ algorithmically. In order to accomplish this we work with the sets of faces incident on each other at a vertex (there are eight of these sets) and orient them by putting a clockwise spin on every vertex, thereby obtaining exactly one cycle of three faces per vertex. This spin is inverted by reflections, effectively removing them from the set of symmetries. (This is the moment to get pen and paper and verify the set of oriented vertex/face cycles.) The code is mostly like what we saw above, except for the following differences.

f := {[2,1,5], [3,1,2], [4,1,3],
      [5,1,4], [6,2,5], [6,3,2],
      [6,4,3], [6,5,4]
      };


minfirst :=
proc(l)
    local minpos, minval, pos;

    minval := l[1]; minpos := 1;

    for pos from 2 to nops(l) do
        if l[pos]<minval then
            minval := l[pos];
            minpos := pos;
        fi;
    od;

    [seq(l[k], k=minpos..nops(l)),
     seq(l[k], k=1..minpos-1)];
end;

cube_cind :=
proc()
         option remember;
         local fA, fB, p, res, count, term;

         fA := map(minfirst, f);

         count := 0; res := 0;

         for p in permute(6) do
             fB := map(minfirst, subs([seq(k=p[k], k=1..6)], fA));
             if fA = fB then
                 count := count+1;
                 term := pet_autom2cycles([seq(k,k=1..6)], p);
                 res := res+ term;
             fi;
         od;

         print(count);

         res/count;
end;