How to color a cube with exactly 6 colors using Polya enumeration theory

Question

I have seen in other questions (Painting the faces of a cube with distinct colours) , and found for myself there are 30 colorings of the cube with exactly 6 colors. My issue is when I use Polya enumeration theory I take the number of colorings up to 6 to be $\frac{1}{24}(6^6+3*6^4+12*6^3+8*6^2)$ (https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem) and subtract the number of colorings up to 5, $\frac{1}{24}(5^6+3*5^4+12*5^3+8*5^2)$ to get 1426. What is wrong with my application of Polya enumeration theory? How could I fix it?

Answer 1

Let $f(m) = \frac{1}{24} (m^6 + 3m^4 + 12m^3 + 8m^2)$.

The problem is that you want to subtract the number of colorings that use 5 out of 6 colors, not the number that use 5 particular colors.

The fix to this approach would be to start by computing $f(6)-6f(5)$, but of course this overcounts some 5-colorings. So we proceed by inclusion-exclusion and find that the answer is $\sum_{i=0}^6 (-1)^i{m\choose i} f(m-i) = f(6) - 6f(5) + 15f(4) - 20f(3) + 15f(2) - 6f(1) = 30$.

---

Another equivalent approach is to compute the exponential generating function $F(X) = \sum_{m=0}^\infty f(m) X^n$.

It turns out that $F(X) = e^X p(X)$, where $p(X)$ is a degree $6$ polynomial. Then $G(X) = e^{-X} F(X) = p(X)$ is the exponential generating function for $g(m)$, the number of colorings with exactly $m$ colors.

We can compute $p$ explicitly, but it is straightforward to see that it has the same leading term as $f$, namely $\frac{1}{24} X^6$.

Then we can compute $g(6) = 6! \cdot [X^6] p(X) = \frac{6!}{24} = 30$.

Answer 2

To find the number of ways to color the faces of a cube with exactly $6$ colors using Polya's Enumeration Theorem:

First, as you already know, the cycle index of the symmetries of the face permutations of a cube is $$Z = \frac{1}{24}(x_1^6 + 6x_1^2x_4+3x_1^2x_2^2 + 8x_3^2 + 6x_2^3)$$ The figure inventory for $6$ colors represented by $a,b,c,d,e,f$ is $$a+b+c+d+e+f$$ "Substituting" the figure inventory into the cycle index, we have $$\frac{1}{24} \left((a+b+c+d+e+f)^6 \\ \\+6 (a+b+c+d+e+f)^2 \left(a^4+b^4+c^4+d^4+e^4+f^4\right) \\+3 (a+b+c+d+e+f)^2 \left(a^2+b^2+c^2+d^2+e^2+f^2\right)^2\\+8 \left(a^3+b^3+c^3+d^3+e^3+f^3\right)^2 \\ +6 \left(a^2+b^2+c^2+d^2+e^2+f^2\right)^3 \right) $$ The number of ways to color the cube using each of the six colors exactly once is the coefficient of $abcdef$ when this polynomial is expanded. In difficult cases I would use a computer algebra to find the coefficient, but in this example it's easy to see that what we want is $1/24$ the coefficient of $abcdef$ in $(a+b+c+d+e+f)^6$, i.e. $$\frac{6!}{24} = 30$$