Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We have a cube and we are coloring its edges. There are three colors available. We say that the two colorings are the same if one can obtain a second by turning cube and permuting colors. Find the number of different colorings.

Any ideas?

I've found Pólya enumeration theorem, but it's difficult to understand for me, also this approach does not take into account the permutation of colors...

share|improve this question

3 Answers 3

up vote 5 down vote accepted

As I started working on this using Burnside's lemma, I might as well show what I've got. It is easy to make a mistake here, so no guarantees. At least I got an answer that passes the lithmus test of being an integer:-)

As described in loc.cit the 24 rotations of the cube split into 5 conjugacy classes. For each class we need to know what kind of orbits a representative in that class (or rather, the cyclic group generated by the representative) has among the edges. We also need to know the cardinality of the class.

$A$: The class of the identity mapping. Its action on the edges has 12 singleton orbits, and $|A|=1$.

$B$: The class of 90 degree rotations. Its action partitions the edges into 3 orbits with 4 edges in each orbit. $|B|=6.$

$C$: The class of 180 degree rotations about an axis connecting the midpoints of an opposite pair of faces of the cube (the squares of elements of class $B$). The edges are partitioned into 6 pairs. $|C|=3.$

$D$: The class of 120 degree rotations about an axis connecting two opposite vertices. The edges are partitioned to 4 orbits, each with 3 edges. $|D|=8.$

$E$: The class of 180 degree rotations about an axis connecting the midpoints of two parallel but opposite edges. The edges are partitioned into 7 orbits: 2 singletons (the ones intersecting the axis) and 5 pairs. $|E|=6.$

The group of color permutations is isomorphic to $S_3$ and has three conjugacy classes: $a$= the class of the identity mapping, $b$= the class of three 2-cycles (this time swapping two colors and leaving the third color as it is), $c$= the class of two 3-cycles.

The cartesian product of order $24\cdot6=144$ then acts on the set $X$ of colorings. The following table lists the number of fixed points in $X$ that an element of the listed conjugacy class has.

$$ \begin{array}{c|c|ccc|c|c} \text{class}&\text{size}&|X^g|&&\text{class}&\text{size}&|X^g|\\ \hline Aa&1&3^{12}&&Cc&6&0\\ Ab&3&1&&Da&8&3^4\\ Ac&2&0&&Db&24&1\\ Ba&6&3^3&&Dc&16&3^4\\ Bb&18&3^3&&Ea&6&3^7\\ Bc&12&0&&Eb&18&3^5\\ Ca&3&3^6&&Ec&12&0\\ Cb&9&3^6&&&& \end{array} $$ Feeding these numbers into the formula of Burnside's lemma tells that the number of orbits (=the number of distinguishable colorings under the prescribed rules) is $$ |X/G|=\frac{1\cdot3^{12}+3\cdot1+6\cdot3^3+18\cdot3^3+3\cdot3^6+9\cdot3^6+8\cdot3^4+24\cdot1+16\cdot3^4+6\cdot3^7+18\cdot3^5}{144}=3882. $$

How did I come up with these numbers. The details vary a bit case-by-case. As somewhat typical examples consider:

The class $Ab$: Here the edges stay at the same place, but two of the colors are interchanged. A coloring is a fixed point of this operation only if it is monochromatic (of the non-interchanged color). Thus the elements in this class have exactly one fixed point.

The class $Ba$: Here we want to calculate the number of colorings that remain unchanged, when we rotate the cube by 90 degrees, and don't do any repainting. For this to happen it is necessary and sufficient that any of the three groups of four edges permuted among themselves by the rotation must share the same color. We have the liberty of choosing the colors for all the orbits independently. Therefore there are $3^3$ such colorings.

The class $Bb$: Here the 3 groups of 4 edges undergo some repainting in addition to the 90 degree rotation. If the three colors are R,Y,G, and we are to repaint every yellow edge green, and every green edge yellow, then for each orbit the possible colorings are RRRR, YGYG and GYGY. In the latter two cases repainting cancels the effect of the rotation. So we have 3 choice for the three groups of 4 edges, and a total of $3^3$ colorings fixed under a group action of this type.

The class $Bc$: Here we can assume a color replacement scheme $Y\mapsto R\mapsto G\mapsto Y$. This permutation of order 3 just doesn't mesh with the rotation of order 4, so no colorings are fixed points for this operation.

The class $Dc$: Let's study the same color replacement scheme as with class $Bc$. The 12 edges are partitioned into 4 groups of 3 edges. The coloring of such a group has to be either $RGY$, $GYR$ or $YRG$ for the repainting to cancel the effect of the rotation. But the choices for the four orbits are independent from each other, so we get a total of $3^4$ colorings that are fixed under an operation of this type.

The class $Eb$: Assume color replacement scheme $R\mapsto R$, $Y\mapsto G\mapsto Y$. For a coloring to be a fixed point, the two edges that are rotated in place, must both be red. But for the 5 pairs of edgese that interchange their locations, the possible colorings are $RR$, $YG$ and $GY$ for the same reasons as with class $Bb$.

If you have trouble filling in the rest of the table, @ping me!

share|improve this answer
    
Your solution looks very good but I get a slightly different value also using Burnside. I have computed these with three different methods (generating functions, two ways, Burnside, one way, see below) so you might want to check your computation. –  Marko Riedel Jun 15 at 2:32

I wrote up a how-to with several detailed examples, including counting the number of ways of coloring the faces of the cube, on my blog. That should get you started. I may be able to come back to this answer later to discuss edge colorings, but it's not very different.

Addendum: Jyrki has done a very thorough discussion of the fixed points of edge colorings under various actions, and I have nothing much to add to his excellent explanantion except that it is often only little more work to do the analysis in general for $N$ colors, and to get a polynomial in $N$, than it is to do it for some particular $N$, as Jyrki did.

share|improve this answer
    
I don't see, why we would get a polynomial in $N$ as a solution to the $N$-colored version of this problem? Are you saying that it is not just a coincidence, that we got a power of 3 e.g. in the case Bb? May be it isn't? I'll give you a bounty, if you can derive a general formula here (that is, without consuming a full paper's worth of space)!! I would have guessed that the number of conjugacy classess of $S_N$ blowing on your face alone would make it mighty hard. +1 for the link to your blog was already there :-) –  Jyrki Lahtonen May 29 '12 at 8:58
1  
@Jyrki: The solution isn't a polynomial in $N$ because it's constant for $N\ge12$ but not constant for $N\le12$. (By the way, that also means it's easy to derive a general formula, since one would merely have to write a program that counts the patterns up to $N=12$. :-) –  joriki Feb 3 '13 at 14:12
    
@joriki: By <insert the name of a deity>! You're right! Neat :-) –  Jyrki Lahtonen Feb 3 '13 at 17:51

I would like to contribute some enrichment material to facilitate additional exploration of this problem. The most important observation is that what we have here is an instance of Power Group Enumeration, with the group acting on the slots where the $n$ colors are placed being the edge permutation group $E$ of the cube and the group acting on the colors being the symmetric group on $n$ elements $S_n$.

We can compute the number of configurations by Burnside's lemma which says to average the number of assignments fixed by the elements of the power group, which has $n!\times |E|$ elements where $|E|=24$. But this number is easy to compute. Suppose we have a permutation $\alpha$ from $E$ and a permutation $\beta$ from $S_n.$ If we place the appropriate number of complete, directed and consecutive copies of a cycle from $\beta$ on a cycle from $\alpha$ then this assignment is fixed under the power group action, and this is possible iff the length of the cycle from $\beta$ divides the length of the cycle from $\alpha$ and there are as many assignments as the length of the cycle from $\beta.$

To do this we first need the cycle index of $E$, which we now compute. There is the identity, which contributes $$a_1^{12}.$$ Rotations about an axis passing through a pairs of opposite vertices contribute $$4\times 2 a_3 ^4.$$ Rotations about an axis passing through opposite faces contribute $$3 \times (2 a_4^3 + a_2^6).$$ Finally rotations about an axis passing through midpoints of opposite edges contribute $$6\times a_1^2 a_2^5.$$

This gives the cycle index $$Z(E) = \frac{1}{24} \left(a_1^{12} + 8 a_3^4 + 6 a_4^3 + 3 a_2^6 + 6 a_1^2 a_2^5\right).$$

Let's verify this cycle index before we proceed. For edge colorings with $n$ colors where the colors are not being permuted we obtain the formula $$\frac{1}{24} \left(n^{12} + 8 n^4 + 6 n^3 + 3 n^6 + 6 n^7\right).$$ This gives the sequence $$1, 218, 22815, 703760, 10194250, 90775566, 576941778, 2863870080,\ldots$$ which points us to OEIS A060530, where we find that indeed we have the right cycle index.

Now the Burnside computation is best done with a CAS, here is the Maple code.

pet_cycleind_symm :=
proc(n)
        local p, s;
        option remember;

        if n=0 then return 1; fi;

        expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;

pet_flatten_term :=
proc(varp)
        local terml, d, cf, v;

        terml := [];

        cf := varp;
        for v in indets(varp) do
            d := degree(varp, v);
            terml := [op(terml), seq(v, k=1..d)];
            cf := cf/v^d;
        od;

        [cf, terml];
end;

cube_edge_cind :=
1/24*(a[1]^12 + 8*a[3]^4 + 6*a[4]^3 + 3*a[2]^6 + 6*a[1]^2*a[2]^5);

cube_edge_colorings :=
proc(n)
    option remember;
    local idx_colors, res, a, b,
    flat_a, flat_b, cyc_a, cyc_b, len_a, len_b, p, q;

    if n=1 then 
       idx_colors := [a[1]]
    else       
       idx_colors := pet_cycleind_symm(n);
    fi;

    res := 0;

    for a in cube_edge_cind do
        flat_a := pet_flatten_term(a);

        for b in idx_colors do
            flat_b := pet_flatten_term(b);

            p := 1;
            for cyc_a in flat_a[2] do
                len_a := op(1, cyc_a);
                q := 0;

                for cyc_b in flat_b[2] do
                    len_b := op(1, cyc_b);

                    if len_a mod len_b = 0 then
                        q := q + len_b;
                    fi;
                od;

                p := p*q;
            od;

            res := res + p*flat_a[1]*flat_b[1];
        od;
    od;

    res;
end;

This will produce the following sequence of values for colorings with at most $n$ colors with the symmetric group acting on the colors: $$1, 114, 3891, 29854, 87981, 143797, 170335, 177160,\ldots$$

Important observation. This is the third solution to this problem, there are two more solutions by the Harary/Palmer method and by Fripertinger's method at this MSE link.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.