In how many rotational distinct ways can we color the vertices of a cube with 2 colors and faces with 4 colors? (This can be interpreted in two ways, either you have to use exactly 4 colors or at most 4. I'm interested in solving it for both conditions).

There are questions and answers for each part separately but I couldn't find a wholesome answer on each part (either coloring only faces or only vertices) also I don't know how to join the two answers.

Any help would be appreciated

  • $\begingroup$ @Dzoooks thanks I edited the question, rotational distinct means if you count a cube in your answer there shouldn't be another one counted if the two can turn into each other by rotation (for example front side red and the rest blue vs. back side red and the rest blue), Also I'm not sure that the two (faces and vertices) are separate, you may be right but it's not that obvious to me $\endgroup$ – Alaleh Ahmadian Jun 23 '18 at 0:02
  • $\begingroup$ @Dzoooks No, you can't count vertex colorings and face colorings separately and multiply the numbers. For instance, if there is just one red vertex and just one red face, we can distinguish between colorings where the red vertex is on the red face and colorings where it isn't. $\endgroup$ – bof Jun 23 '18 at 2:37

A mixed cycle index for faces and vertices combined can be of use in this problem. We can then apply Burnside or Polya as desired. The group $H$ here are the rotations permuting six faces and eight vertices simultanteously, acting on fourteen slots for the colors. We use $b_q$ for the cycles of the vertices and $a_q$ for the faces.

We proceed to enumerate the permutations of this group. There is the identity, which contributes $$a_1^6 b_1^8.$$

There are three rotations for each pair of opposite faces that fix those faces (rotate about the axis passing through the center of the two faces). The vertices on the two faces are in four-cycles or two-cycles, for a contribution of

$$3\times (2 a_1^2 a_4 b_4^2 + a_1^2 a_2^2 b_2^4).$$

There are rotations about an axis passing through opposite vertices, of which there are four pairs. These fix those vertices and put the rest on three-cycles, giving

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

Finally we may rotate about an axis passing through the centers of opposite edges and there are six of these. These rotations partition the vertices into two-cycles, giving

$$6\times a_2^3 b_2^4.$$

It follows that the cycle index of $H$ is given by

$$Z(H) = \frac{1}{24} \left(a_1^6 b_1^8 + 6 a_1^2 a_4 b_4^2 + 3 a_1^2 a_2^2 b_2^4 + 8 a_3^2 b_1^2 b_3^2 + 6 a_2^3 b_2^4\right).$$

Using at most $N$ colors for the faces and $M$ for the vertices we get for the number of colorings by Burnside

$$\bbox[5px,border:2px solid #00A000]{ H(N, M) = \frac{1}{24}(N^6 M^8 + 6 N^3 M^2 + 3 N^4 M^4 + 8 N^2 M^4 + 6 N^3 M^4).}$$

Setting $M=1$ here we should get face colorings. We obtain

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

and we encounter OEIS A047780 where we see that we have the right values. Setting $N=1$ yields vertex colorings:

$$1, 23, 333, 2916, 16725, 70911, 241913, 701968, \ldots$$

which points to OEIS A000543 which is correct as well.

Continuing with the question of colorings that use exactly $N$ colors for the faces and exactly $M$ for the vertices we find using Stirling numbers for set partitions

$$\bbox[5px,border:2px solid #00A000]{ \begin{gather} H_X(N, M) = \frac{N! \times M!}{24} \\ \times \left({6\brace N} {8\brace M} + 6 {3\brace N} {2\brace M} + 3 {4\brace N} {4\brace M} + 8 {2\brace N} {4\brace M} + 6 {3\brace N} {4\brace M}\right). \end{gather}}$$

Setting $M=1$ here we get the count of face colorings with exactly $N$ colors:

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

Note that for six colors, which is the maximum, the orbits have size $24$ because all the colors are distinct and indeed $6!/24 = 30.$ Similarly with $N=1$ we get vertex colorings:

$$1, 21, 267, 1718, 5250, 7980, 5880, 1680, 0, \ldots$$

and once more for eight colors, the maximum possible, we find that $8!/24 = 1680.$

Concluding we get for at most two vertex colors and at most four face colors

$$H(4,2) = 44608$$

and for exactly two vertex colors and four face colors

$$H_X(4,2) = 16552.$$


We have to write some cycle indices. By Maple, the two permutation groups are 6T8 and 8T14.

For G acting on faces we have : ${1 \over 24 } (x_1^6 + 3.x_1^2x_2^2 + 6x_2^3+ 6x_1^2x_4 + 8.x_3^2 )$

For G acting on vertices we have : ${1 \over 24 } (y_1^8 + 3.y_2^4 + 6.y_2^4 + 6.y_4^2 + 8.y_1^2.y_3^2 )$

For G acting on both, the cycle index is

${1 \over 24 } (x_1^6y_1^8 + 3x_1^2x_2^2y_1^8 + 6x_2^3y_2^4+ 6x_1^2x_4y_4^2 + 8x_3^2y_1^2y_3^2 )$

Polya method means essentially to associate a 'colored permutation' to a colored partition, establishing a one-to-one correspondence between colored permutations and fixed points.

e.g. $ \color {red} {(A)} \color {green} {(B)} \color {blue} {(C)} \color {green} {(D , E, F)} $ is associated to a colored partition $ \color {red} A \ | \color {green} {B, D, E, F} \ | \ \color {blue} C\ $

Since the sets of faces and vertices do not overlap, neither do the cycles that form a "colored permutation". We may safely count them using the multiplication principle. Thus, passing to m and n we get

${1 \over 24 } (m^6n^8 + 3m^4n^4 + 6 m^3n^4 + 6m^3n^2 +8m^2n^4)$

Eventually we obtain a generating function like

$AtMost(x) = 0 + x + 10x^2 + 57x^3 +240x^4 + 800x^5 + 2226x^6 +5390x^7+ \cdots$

when we still need

$Exact(x) = 0 + x + 8x^2 + 30x^3 + 68x^4 + 75x^5 + 30x^6 + 0 + 0 + \cdots$

The two GF's are related. For example, $57 = {3\choose 3}30 + {3\choose 2}8 + {3\choose 1} 1 + {3\choose 0}0 $ meaning that at most three colors are obtained adding configurations of actually three colors to configurations having pairs of colors and so on.

Reversely, the coefficient of $x^k$ in $Exact$ g.f. is extracted from $AtMost$ by $coeff \ ( \ Exact(x), x^k \ ) \ = coeff \ ( \ AtMost(x)(1-x)^k \ ) $

Within respect with the previous studied example $H(4,2)$, taken into account both variables

"at most" $0, 23, 776, 8121, 44608$ produce "exact" values $0, 23, 730, 5863, 16688$

"at most" $0, 1, 10, 57, 240$ produce "exact" values $0, 8 , 30 , 68$

Then we extract the exact value $H_X(4,2) = 16552 = 16688 - 2\times68$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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