4
$\begingroup$

I am searching for the number of uniques ways to paint an icosahedron. However, my understanding of mathematics is quite limited in the field of combination and permutation. I have searched through many pages in google and herein but found myself unable to translate simple terms such as "repitition" to fit my question. I would be thankful for hints which help me in solving this question.

I have five silver balls and eight golden balls, and have to arrange them in icosahedral shape wherein the thirteenth position is in the centre.

In the first step I would like to calculate how many possible ways there are to arrange silver and golden balls over these thirteen positions. If I am correct, the answer is 91. I assumed it to by combinatorial problem with repition (is that right?). $$x = \frac{(n+r-1)!}{r!(n-1)!} = \frac{(13+2-1)!}{2!(13-1)!} = 91$$ where $n$ is the number of things to choose from, and we choose $r$ of them.

Now I would like to know how unique ways there are. If I compare two possibilities and I am able to show that they are identical simply by rotating the icosahedral arrangement, I would like to discard one of these. How can I implement this into calculations? ...

Please note, that this is not homework. This is an actual question I ask myself.

$\endgroup$
  • 2
    $\begingroup$ If I have understood your problem correctly, I think the answer to the first part should be $C(13,5)=1287$. This is if you think of the arrangement of silver and gold balls as being fixed in space. If you want to discount arrangements which are "equivalent by rotation" it is a more intricate problem, but if you Google "burnside orbit counting examples" or maybe "burnside orbit counting icosahedron" you should find something helpful. $\endgroup$ – David Feb 26 '15 at 12:36
  • $\begingroup$ Please excuse me, I was in such a hurry that I did not reply here to you. Thank you very much! The term "Burnside" helped me a lot. This helped me further in understanding (for everyone reading this comments section): ringomok.com/mathematics/combinatorics/burnsides-lemma $\endgroup$ – Crystal Lettuce Feb 28 '15 at 20:02
  • $\begingroup$ You're welcome! Glad the suggestion was helpful. $\endgroup$ – David Mar 1 '15 at 11:13
5
$\begingroup$

Remark. I somehow missed the fact that this is a duplicate question. This is the MSE link to the original computation, which did not include the PIE component.

The number of different isomers can be calculated by an application of the Polya Enumeration Theorem (PET) to the vertex permutation group of the regular icosahedron. We will not be concerned with the central vertex as it is fixed by all rotations and only adds a factor of two to the result. The general case that includes reflections can be challenging and may require assistance from a computer algebra system but rotations only are just simple enough that they can be done using pen and paper and your imagination (it seems difficult to mentally reflect an icosahedron through its center and factor the resulting permutation).

We will now compute the cycle index $Z(Q)$ of the vertex permutation group $Q$ of the regular icosahedron in order to apply PET. As this is the dual of the regular dodecahedron and the dodecahedron is somewhat simpler to work with we will use the dodecahedron and calculate the face permutation group of the regular dodecahedron, which can be seen at this Wikipedia entry.

We enumerate the permutations in this group. There is the identity, which contributes $$a_1^{12}.$$ There are two rotations about an axis passing through any one of ten pairs of opposite vertices, which contributes $$10\times 2\times a_3^4.$$ There are four rotations about an axis passing through the centers of any one of six pairs of opposite faces, for a contribution of $$6\times 4\times a_1^2 a_5^2.$$ Finally there is a rotation about an axis passing through the centers of any one of fifteen pairs of opposite edges, for a contribution of $$15\times a_2^6.$$

This gives the following cycle index: $$Z(Q) = \frac{1}{60} \left(a_1^{12} + 20a_3^4 + 24 a_1^2 a_5^2 + 15 a_2^6\right).$$

which in turn gives the following generating function for two colors / two types of atoms: $${\frac { \left( 1+z \right) ^{12}}{60}}+1/4\, \left( {z}^{2}+1 \right) ^{6}+2/5\, \left( 1+z \right) ^{2} \left( {z}^{5}+1 \right) ^{2} +1/3\, \left( {z}^{3}+1 \right) ^{4}$$ or alternatively $${z}^{12}+{z}^{11}+3\,{z}^{10}+5\,{z}^{9}+12\,{z}^{8}+14\,{z}^{7} \\+24\,{z}^{6}+14\,{z}^{5}+12\,{z}^{4}+5\,{z}^{3}+3\,{z}^{2}+z+1.$$

This is indexed by the number of instances of the one type of atom. Answering the OPs question, if you put a silver atom in the center that leaves four silver, eight gold, and the generating function says that there are $12$ isomers. If you put a gold atom in the center that leaves five silver and seven gold and the generating function says there are $14$ isomers.

With $N$ different colors we obtain the sequence $$1, 96, 9099, 280832, 4073375, 36292320, 230719293, \\ 1145393152, 4707296613, 16666924000,\ldots$$

which points us to OEIS A000545 where the above calculation is confirmed.

Note that we can derive a formula for the case of $N$ colors by using the fact that it is given by $$Z(Q)(C_1+C_2+\cdots+C_N)_{C_1=1, C_2=1, \ldots C_N=1}.$$ This yields $$a_N = \frac{1}{60} \left(N^{12} + 44N^4 + 15 N^6\right).$$

The sequence $\{a_N\}$ counts colorings using at most $N$ colors and we need to use the principle of inclusion-exclusion (PIE) to get the number of colorings with exactly $M$ colors, call this sequence $\{b_M\}.$

We have $$b_M = \sum_{N=1}^M {M\choose N} (-1)^{M-N} a_N.$$ This gives the sequence $$1, 94, 8814, 245008, 2759250, 15884004, 52701264, 106866144, \\ 134719200, 103118400, 43908480, 7983360, 0, 0, 0, 0,\ldots$$ which is finite because there are only twelve vertices available for coloring and hence no coloring with thirteen different colors, etc.

Observe that $$\frac{12!}{60} = 7983360$$ which is because with twelve different colors all orbits have the same size, namely $60.$

This list at MSE Meta has many more Polya / Burnside computations by various users.

$\endgroup$
  • $\begingroup$ What we have here matches the data at MathWorld which is linked to from the OEIS entry. $\endgroup$ – Marko Riedel Feb 26 '15 at 23:22
  • $\begingroup$ That's what it means. And using exactly two colors as opposed to at most two colors there are $94$ colorings ($96$ colorings minus two monocrome colorings). $\endgroup$ – Marko Riedel Feb 28 '15 at 20:29

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.