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?
Color a cube with exactly 6 colors using Polya enumeration theory
combinatoricsdiscrete mathematicspolya-counting-theorysolution-verification
Best Answer
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$.