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

combinatorics

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

Best Answer

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.