3
$\begingroup$

Given a multiset of colored edges $A$, $|A| = 30$ I want to know the number of distinct dodecahedra that can be constructed using these edges. Two dodecahedra are equal if one of them is a rotation of another dodecahedron.

By labeling colors with numbers $n$, $n \in \{1,...,30\}$ I can give the following multisets as an example:

  1. For $A = \{1,...,1\}$ or $A = \{1, 2,...,2\}$ the answer is obviously $1$.

  2. For $A = \{1, 1, 2,...,2\}$ it is $11$.

This problem should probably be solved using Burnside's lemma.

To start with, here is the description of dodecahedron's symmetry group.

There are $24$ rotations that fix $6$ edges, $20$ ones that fix $10$, $15$ rotations fixing $16$ edges each and one rotation fixing all $30$ edges.

Therefore, by Burnside's lemma the answer should be $\frac{1}{60}(a_1 + 24a_2 + 20a_3 + 15a_4)$ where $60$ is the order of $A_5$. I also found OEIS A282670 number of ways to color edges of a dodecahedron with at most $n$ colors.

The problem is that I don't know what these $a_i$ should be (and I'm actually not sure the answer should look like that at all). My best guess for that $a_1$ is the permutation of a multiset (for the second example it would be the case $a_1 = \frac{30!}{2!28!}$ ) and remaining $a_i$ would be k-permutations of a multiset for which I failed to find an explicit formula (this question has an example of such permutations), where $k$ would be the number of edges fixed by a rotation.

Could you help me please?

$\endgroup$
2
$\begingroup$

Following the approach at this MSE link we compute the cycle index of the permutation group of the edges. Using the image at Wikipedia we see that there are three types of symmetries in addition to the identity: rotations about an axis passing through the centers of two opposite faces, rotations about an axis passing through opposite vertices and $180$ degree rotations that flip two opposite edges, mapping each onto itself.

The identity contributes the following term to the cycle index: $$ a_1^{30}.$$

There are six pairs of opposite faces and four rotations for each of these about an axis passing through the centers of the pair which turn everything into five-cycles since the faces other than the chosen pair also form five-cycles, which applied to the edges gives

$$ 6 \times 4 \times a_5^6 = 24 a_5^6.$$

There are ten pairs of opposite vertices and two rotations by $120$ and $240$ degrees for each of these which create two three-cycles at the two vertices. The two rotations create two three-cycles among the faces not adjacent to the two vertices and this carries over to the edges of these faces (the remaining six faces not incident with the pair share one and two edges with the three faces incident at each vertex of the pair and the rotation preserves this property), giving

$$ 10 \times 2 \times a_3^{10}.$$

There are fifteen pairs of opposite edges and the $180$ degree rotations about the plane passing through them fix those edges and partition everything else into two-cycles, giving

$$ 15 \times a_1^2 a_2^{14}.$$

It follows that the cycle index of the permutation group $G$ of the edges is

$$ Z(G) = \frac{1}{60} \left( a_1^{30} + 24 a_5^6 + 20 a_3^{10} + 15 a_1^2 a_2^{14}\right).$$

Substituting into the cycle index we obtain the explicit formula for $N$ colors

$$\frac{1}{60} \left(N^{30} + 24 N^6 + 20 N^{10} + 15 N^{16}\right) = \frac{1}{60} N^{30} + \frac{2}{5} N^6 + \frac{1}{3} N^{10} + \frac{1}{4} N^{16}.$$

We obtain the sequence

$$1, 17912448, 3431529649899, 19215359484207104, \\ 15522042948408209375, \ldots $$

which points us to OEIS A282670 where these data are confirmed.

Next suppose we have $q$ different colors and a multiset drawn from these colors and we ask about the number of colorings with this multiset. We use the Polya Enumeration Theorem, which yields

$$ Z(G)(A_1+\cdots +A_q) = \\ \frac{1}{60} \left( (A_1+\cdots +A_q)^{30} + 24 (A_1^5+\cdots +A_q^5)^6 + 20 (A_1^3+\cdots +A_q^3)^{10} \\ + 15 (A_1+\cdots +A_q)^2 (A_1^2+\cdots +A_q^2)^{14}\right).$$

E.g. for two colors with one color appearing twice we need the coefficient on $[A_1^2 A_2^{28}].$ We get

$$\frac{1}{60} \left( {30\choose 2} + 15 + 15 {14\choose 1} \right) = 11$$

as claimed. As a concluding observation we also obtain for colorings with exactly $M$ colors the closed form

$$\frac{M!}{60} \left({30\brace M} + 24 {6\brace M} + 20 {10\brace M} + 15 {16\brace M}\right).$$

This yields a finite sequence from $M=1$ to $M=30$ (the maximum possible with all edges different)

$$1, 17912446, 3431475912558, 19201633473082192, 15426000466104548370, \ldots, 1879979643918904128084836352000000, \\ 438404032189593555246120960000000, 64102774454612839170441216000000, \\ 4420880996869850977271808000000.$$

We see in the second term that the two monochrome colorings have been subtracted and the last one is $30!/60$ (with all edges unique we have that all orbits are the same size).

$\endgroup$
  • $\begingroup$ The answer is just brilliant, it took me a while to process it though. $\endgroup$ – Atin Jan 31 '18 at 20:38

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.