4-coloring the faces of a cube

Question

How many ways to color the faces of a cube in 4 colors if methods that differ in self-alignment of the cube are considered equal(it means as i think that rotations and reflections do not make any difference and we consider such motions as equal)?

I found quite the same problem, the solution was based on finding the symmetry group with 24 elements (rotations) and we could count the ways using Bernsides lemma (1/24*(4^6+6*4^3+3*4^4+8*4^2+6*4^3)) and we got 240. I was told to look through reflections (group of 48 elements). How do I have to count in this case? How will the finite formula look like? Help me, please

Answer 1

With this problem the key observation is that when combining rotations and reflections of the cube we actually get all automorphisms. These are given for the $d$-cube by labeling the vertices with $d$ bits from zero to $2^d-1$ and combining the $2^d$ possible bit flips with the $d!$ possible bit permutations, for a total of $48$ automorphisms when $d=3.$ Hence the cycle index is easy to compute, combining the flips and permutations to obtain a vertex permutation, apply that to the faces, and factor the result into disjoint cycles. This is shown below.

with(combinat);

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

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

    marks := Array([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;


pet_cycleind_cube_face :=
proc()
option remember;
local faces, verts, vidx, vert,
    flp, perm, subl, ind, cind;

    verts :=
    [[0,0,0], [0,0,1], [0,1,0], [0,1,1],
     [1,0,0], [1,0,1], [1,1,0], [1,1,1]];

    faces :=
    [{0,1,2,3}, {4,5,6,7},
     {0,1,4,5}, {2,3,6,7},
     {0,2,4,6}, {1,3,5,7}];

    cind := 0;

    for flp to 8 do
        perm := firstperm(3);

        while type(perm, list) do
            subl := [];

            for vidx to 8 do
                vert :=
                [seq((verts[flp][ind] +
                      verts[vidx][perm[ind]]) mod 2,
                    ind=1..3)];

                subl :=
                [op(subl), vidx-1 = 4*vert[1]+2*vert[2]+vert[3]];
            od;

            cind := cind +
            pet_autom2cycles(faces, subs(subl, faces));

            perm := nextperm(perm);
        od;
    od;

    cind/48;
end;

We get the following cycle index:

$$Z(F) = 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\,{a_{{2}}}^{3}}{48}} +1/8\,a_{{2}}a_{{4}}+1/6\,{a_{{3}}}^{2}+1/6\,a_{{6}}.$$

We then have by Burnside the following formula for the number of colorings using at most $N$ colors:

$$1/48\,{N}^{6}+1/16\,{N}^{5}+3/16\,{N}^{4} +{\frac {13\,{N}^{3}}{48}}+{\frac {7\,{N}^{2}}{24}}+N/6.$$

This was computed from the cycle index as shown below:

cube_face_colorings :=
proc(N)
option remember;
local var, cind, subl;

    cind := pet_cycleind_cube_face();
    subl := [seq(var = N, var in indets(cind))];

    subs(subl, cind);
end;

We get the following sequence:

$$1, 10, 56, 220, 680, 1771, 4060, 8436, \\ 16215, 29260, 50116, 82160, \ldots$$

This points us to OEIS A198833, where these data are confirmed and we also find the cycle index. The value for $N=4$ (at most four colors) is

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

Remark. We have for the number of colors being exact the closed form

$$\frac{N!}{48} \left( {6\brace N} + 3{5\brace N} + 9 {4\brace N} + 13 {3\brace N} + 14 {2\brace N} + 8{1\brace N} \right).$$

This yields the finite sequence of exact colorings (six faces admit at most six different colors):

$$1, 8, 29, 52, 45, 15.$$

This points to OEIS A325009 where these data are once more confirmed. We get for exactly four colors

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

When $N=6$ all orbits contain $48$ configurations (distinct, no symmetries) and we get $6!/48 = 15.$