# Counting distinguishable ways of painting a cube with 4 different colors (each used at least once)

You have many identical cube-shaped wooden blocks. You have four colors of paint to use, and you paint each face of each block a solid color so that each block has at least one face painted with each of the four colors. Find the number of distinguishable ways you could paint the blocks. (Two blocks are distinguishable if you cannot rotate one block so that it looks identical to the other block.)

Having trouble solving this problem with the added constraint of "at least one face painted with each of four colors" - Thanks in advance

Call the four colors $a$, $b$, $c$, $d$.

There are two partitions of $6$ into four parts, namely (1): $(3,1,1,1)$, and (2): $(2,2,1,1)$.

In case (1) we can choose the color appearing three times in $4$ ways. This color can either (1.1) appear on three faces sharing a vertex of the cube, or (1.2) on three faces forming a $\sqcup$-shape. In case (1.1) we can place the three other colors in $2$ ways ("clockwise" or "counterclockwise"); in case (1.2) we can choose which of the three other colors is opposite the floor of the $\sqcup$. This amounts to $4\cdot(2+3)=20$ different colorings.

In case (2) the two colors appearing only once can be chosen in ${4\choose2}=6$ ways. Assume that colors $a$ and $b$ are chosen. The $a$-face $F_a$ and the $b$-face $F_b$ can be either (2.1) opposite or (2.2) adjacent to each other. In case (2.1) we can chose the two $c$-faces either adjacent or opposite to each other. In case (2.2) the two $c$-faces can be (2.2.1) opposite to each other, (2.2.2) opposite to $F_a$ and to $F_b$, or (2.2.3) opposite to one of $F_a$ or $F_b$ and on one of the faces adjacent to both $F_a$ and $F_b$. In all this amounts to $6\cdot(2+1+1+2\cdot2_*)=48$ different colorings. (The factor $2_*$ distinguishes mirror-equivalent colorings.)

Altogether we have found $68$ different admissible colorings of the cube.

• great solution ! - I still need to work out the second scenario in detail but appears to be a valid solution. Thanks – randomwalker Apr 18 '17 at 21:15

There is an algorithmic approach to this which I include for future reference and which consists in using Burnside and Stirling numbers of the second kind. For Burnside we need the cycle index of the face permutation group of the cube. We enumerate the constituent permutations in turn. First there is the identity for a contribution of $$a_1^6.$$

Rotating about one of the four diagonals by $120$ degrees and $240$ degrees we get

$$4\times 2a_3^2.$$

Rotating about an axis passing through opposite faces by $90$ degrees and by $270$ degrees we get

$$3\times 2 a_1^2 a_4$$

and by $180$ degrees

$$3\times a_1^2 a_2^2.$$

Finally rotating about an exis passing through opposite edges yields

$$6\times a_2^3.$$

We thus get the cycle index

$$Z(G) = \frac{1}{24} (a_1^6 + 8 a_3^2 + 6 a_1^2 a_4 + 3 a_1^2 a_2^2 + 6 a_2^3).$$

As a sanity check we use this to compute the number of colorings with at most $N$ colors and obtain

$$\frac{1}{24}(N^6 + 8 N^2 + 12 N^3 + 3 N^4).$$

This gives the sequence

$$1, 10, 57, 240, 800, 2226, 5390, 11712, 23355, 43450, \ldots$$

which is OEIS A047780 which looks to be correct. Now if we are coloring with $M$ colors where all $M$ colors have to be present we must partition the cycles of the entries of the cycle index into a set partition of $M$ non-empty sets. We thus obtain

$$\frac{M!}{24} \left({6\brace M} + 8 {2\brace M} + 12 {3\brace M} + 3{4\brace M}\right).$$

This yields the finite sequence (finite because the cube can be painted with at most six different colors):

$$1, 8, 30, 68, 75, 30, 0, \ldots$$

In particular the value for four colors is $68.$ We also get $6!/24 = 30$ for six colors because all orbits have the same size.

Here's my crack at it: Starting with a stationary cube, there are $\frac{4 \cdot 3 \cdot 6!}{2 \cdot 2}$ ways of painting the cube where there are 2 colors with 2 faces, and $\frac{4 \cdot 6!}{3}$ ways of painting the cube when there is 1 color with 3 faces which gives a total of 3120 ways of painting the cube, but this over counts all the orientations of a cube, so the final answer is $\frac{3120}{4 \cdot 6} = 130$

• awright96 - Thank you for taking the time to answer the question. I understand your approach which is a good, clean approach. However the correct answer is 68. This problem appeared on a middle-school purple comet test in 2015 ( unfortunately only answers are published, no solutions) – randomwalker Apr 18 '17 at 19:31