1
$\begingroup$

This question already has an answer here:

Find the generating functions in variables $r,b,g$ for the number of ways to paint a dodecahedron red,blue and green.

For example the coefficient of $r^5b^4g^3$ should be the number of ways to paint the dodecahedron with 5 red faces, 4 blue faces and 3 green faces.

I know that we should use Polya's enumeration theorem but I have no idea how to continue. Any solutions are appreciated.

Also it is allowed to be that r=0,or b=0 or g=0

$\endgroup$

marked as duplicate by ml0105, Jyrki Lahtonen Aug 12 '15 at 18:12

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ IMO the key question is: Are two colorings considered to be different, if they are gotten from each other by a symmetry of the dodecahedron (a rotation, a reflection or a combination of the two)? $\endgroup$ – Jyrki Lahtonen Aug 12 '15 at 11:11
  • $\begingroup$ No they are considered to be the same @Jyrki $\endgroup$ – Tommy Aug 12 '15 at 11:15
  • $\begingroup$ Nice autocorrect error! Poor Prof. Polyp! $\endgroup$ – Rob Arthan Aug 12 '15 at 12:33
  • $\begingroup$ Tommy, care to explain why you (or your namesake) asked this question again? This is a dup of this one asked by Tommy yesterday. It is against the rules to reask the same question. You should improve the older one instead. $\endgroup$ – Jyrki Lahtonen Aug 12 '15 at 18:08
  • $\begingroup$ I am closing this, because this was asked in bad faith. $\endgroup$ – Jyrki Lahtonen Aug 12 '15 at 18:12
2
$\begingroup$

Let $G$ be the symmetry group of rotations for the dodecahedron.
Following this answer, we know its cycle index is equal to

$$Z(G) = \frac{1}{60} \left( a_1^{12} + 24 a_1^2 a_5^2 + 20 a_3^4 + 15 a_2^6\right).$$ It tells us the symmetry group $G$ consists of $60$ permutations:

  • $\phantom{0}1$ permutation which is a product of twelve $1$-cycles. i.e the identity.
  • $24$ permutations which is a product of two $1$-cycles and two $5$-cycles.
  • $20$ permutations which is a product of four $3$-cycles.
  • $15$ permutations which is a product of six $2$-cycles.

Let's say we are going to color the faces of a dodecahedron with $n$ colors $c_1, c_2, \ldots, c_n$.
Burnside's Lemma tell us the number of ways is equal to

$$\frac{1}{|G|}\sum_{g\in G} |X_g|$$

where $X_g$ is the set of colorings (by colors $c_1, c_2, \ldots c_n$ ) invariant under the action of $g$.

Consider the case $g$ is a product of $m$ disjoint cycles of length $\ell_1, \ell_2, \ldots, \ell_m$ with $\sum_{j=1}^m \ell_j = 12$.
If a coloring is invariant under $g$, then every face belongs to same cycle need to have same color. The $j^{th}$ cycle of length $\ell_j$ will contribute a factor $c_1^{\ell_j} + c_2^{\ell_j} + \cdots + c_n^{\ell_j}$ to the GF.

This leads to one simplified variant of Pólya enumeration Theorem:

To compute the generating function for $n$ colors $c_1, c_2, \cdots, c_n$,
replace every appearance of $a_k$ in the cycle index by $c_1^k + c_2^k + \cdots + c_n^k$.

Apply these to the case of $3$ colors $r, g, b$, the generating function we seek is given by

$$\frac{1}{60} \left( (r+g+b)^{12} + 24 (r+g+b)^2 (r^5+g^5+b^5)^2 \\+ 20(r^3+g^3+b^3)^4 + 15 (r^2+g^2+b^2)^6\right)$$

$\endgroup$
  • $\begingroup$ +1 This passes the obvious lithmus test that the coefficients of all monomials are integers. I checked that with Mathematica (that's how I spotted that one small typo). $\endgroup$ – Jyrki Lahtonen Aug 12 '15 at 18:02

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