# coloring cube, additional constraint, three colors

I have to paint nodes of cube such that opposing nodes has the same color.

We consider identical cubes such that rotatating.

My result is $15$

Is it correct ?

Ok, I 'll add my way to get a result. $G$ is group of rotating. $$G = \{id, o_1,o_2,o_3,r_1,..,r_1, ..., r_6, s_1,...,s_6,k_1,....,k_8\}\\ |G|=24$$ Const points with respect to $id$: $3^4$

Const points with respect to $o_i$: $3*3^2$

Const points with respect to $r_i$: $6 * 3$

Const points with respect to $s_i$: $6 * 3^3$

Const points with respect to $k_i$: $8*3*3$

Finally: $$\frac{1}{24} (3^4 + 3 * 3^2 + 6 * 3 + 6*3^3 +8* 3 * 3) = 15$$

• Could you add to this the method you used to get 15? – coffeemath Sep 5 '14 at 0:24
• I edited my post – xawey Sep 5 '14 at 8:06

You used Polya counting theory and arrived at $15$, but are not convinced. So let's count the colorings of the four space diagonals again, this time using "brute force".

There are $3$ colorings using just one color.

If we restrict to just two colors we can do it in a $(3,1)$-way or in a $(2,2)$-way. For the $(3,1)$-way we can select the primary color in three ways and the secondary color in two ways. After the colors have been chosen there is just one way to color the diagonals, so that we obtain $6$ colorings of this sort. For the $(2,2)$-way we can select the two colors to be used in three ways. After the colors have been chosen there is just one way to color the diagonals, so that we obtain $3$ colorings of this sort.

If we use all three colors one of them, which can be chosen in $3$ ways, is used twice, and the other two colors are used once. Paint any two diagonals with these two colors and the remaining two with the chosen color – it always looks the same. It follows that we obtain $3$ colorings of this sort.

So it comes to $15$ colorings, as you have found out using the group theoretical approach.

This can also be done using the Polya Enumeration Theorem. With this in mind we need the cycle index $Z(G)$ of the group $G$ of rotations of the cube acting on the four diagonals.

There is the identity, which fixes the diagonals and contributes $a_1^4.$ There are $90$ degree and $270$ degree rotations about an axis passing through the midpoints of opposite faces, giving $3\times 2\times a_4.$ The $180$ degree rotations about these axes contribute $3\times a_2^2.$ Rotations about one of the four diagonals contribute $4\times 2 \times a_1 a_3.$ Finally there are flips about an axis passing through the midpoints of opposite edges, giving $6\times a_1^2 a_2.$

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

Substituting three colors into this cycle index we obtain $$1/24\, \left( A+B+C \right) ^{4}+1/4\, \left( A+B+C \right) ^{2} \left( {A}^{2}+ {B}^{2}+{C}^{2} \right)\\ +1/3\, \left( A+B+C \right) \left( {A}^{3}+{B}^{3}+{C}^ {3} \right) +1/8\, \left( {A}^{2}+{B}^{2}+{C}^{2} \right) ^{2}\\+1/4\,{A}^{4}+1/4 \,{B}^{4}+1/4\,{C}^{4}$$ which expands into $${A}^{4}+{A}^{3}B+{A}^{3}C+{A}^{2}{B}^{2}+{A}^{2}BC+{A}^{2}{C}^{2}+A{B}^{3}+A{B}^ {2}C+AB{C}^{2}\\+A{C}^{3}+{B}^{4}+{B}^{3}C+{B}^{2}{C}^{2}+B{C}^{3}+{C}^{4}.$$ We see that there are indeed $15$ colorings.

More generally for the case of at most $N$ colors we obtain $$\frac{1}{24}(N^4 + 6N + 11N^2 + 6N^3) = {N+3\choose 4}$$ which gives the sequence $\{a_N\}$ $$1, 5, 15, 35, 70, 126, 210, 330, 495, 715, \ldots.$$

This is because the sequence of colorings $\{b_M\}$ using exactly $M$ colors, which is finite (there are only four diagonals available) is $$1,3,3,1,0,0,0,0,\ldots$$ and $${N\choose 1} +3{N\choose 2}+3{N\choose 3}+{N\choose 4} = {N+3\choose 4}.$$

The four initial values of $\{b_M\}$ can be computed by inspection or using the inclusion-exclusion formula $$b_M = \sum_{N=1}^M {M\choose N} (-1)^{M-N} a_N = \sum_{N=1}^M {M\choose N} (-1)^{M-N} {N+3\choose 4}.$$

Addendum. The cycle index can also be computed by enumerating the rotations of the cube and letting them act on the diagonals. The cycle index is then obtained by adding the factorizations into disjoint cycles of the permutations of the diagonals that are obtained. This is what the following Maple code does, which serves to verify the preceding results. It yields the following cycle index:

$$1/24\,{a_{{1}}}^{4}+1/4\,{a_{{1}}}^{2}a_{{2}}+1/3\,a_{{1}}a_{{3}}+ 1/8\,{a_{{2}}}^{2}+1/4\,a_{{4}}$$

which is of course the same as above. The sequence of colorings is $$1, 5, 15, 35, 70, 126, 210, 330, 495, 715, \ldots$$ which is also the same as above.

with(group);

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;

pet_cycleind_cubediag :=
proc()
local pg, els, idx, el, listel, diags, pdiags;

pg := permgroup(8, {[[1,2,4,3], [5,6,8,7]],
[[1,6,7], [2,8,3]],
[[5,6], [4,3], [2,7], [1,8]]});

diags := [{1,8}, {2,7}, {3,6}, {5,4}];

idx := 0; els := elements(pg);

for el in els do
listel := convert(el, 'permlist', 8);
pdiags :=
map(d -> map(ent -> listel[ent], d), diags);

idx := idx + pet_autom2cycles(diags, pdiags);
od;

idx/nops(els);
end;

v :=
proc(n)
option remember;
local sl, q;

sl := [seq(a[q]=n, q=1..4)];
subs(sl, pet_cycleind_cubediag());
end;