5
$\begingroup$

Fifteen balls including 3 each of 5 different colors are arranged in a triangle as shown. How many ways can this be done if rotations are allowed?

fifteenballs

I was thinking the answer should be $15!/(3*(3!)^5)$ as we can arrange 15 balls in 15 positions in 15! ways. Then since there are 3 balls of 5 different colors each, we divide it by $(3!)^5$ and then divide by 3 as rotation is allowed.

But this is not correct as if 6 balls are needed to arrange like this where there are 3 balls each of 2 different colors, by this logic, the answer should be $6!/3!3!3$ which is not an integer.

$\endgroup$
  • $\begingroup$ See Burnside's Lemma . $\endgroup$ – N. F. Taussig Aug 24 '18 at 2:39
  • $\begingroup$ @MishaLavrov Burnside's lemma is applicable: You let X be the set of all ways of coloring the balls with five colors such that each color is represented three times, and G be the group of rotations. $\endgroup$ – Alex Zorn Aug 24 '18 at 2:58
  • $\begingroup$ @AlexZorn Never mind, you're right. $\endgroup$ – Misha Lavrov Aug 24 '18 at 3:04
4
$\begingroup$

This is almost exactly the correct answer. The error lies in rotationally symmetric arrangements.

The way I prefer to think about it is to say that a "picture" is a representation of an arrangement of $15$ balls where we draw all $15$ of them in a triangle (something like the image in the diagram, but colored differently). We can count the pictures easily: there are $\frac{15!}{3!^5}$ pictures, because we just choose the colors of the balls. There are no rotations to worry about.

Almost every arrangement of $15$ balls has exactly $3$ pictures to go with it. However, some arrangements are rotationally symmetric, and in that case, there is only $1$ picture.

There are exactly $5!$ rotationally symmetric arrangements: up to permuting the colors of the balls, they have to be the arrangement represented by the picture below.

enter image description here

So there are $5!$ pictures representing $5!$ symmetric arrangements, which means that the remaining $\frac{15!}{3!^5} - 5!$ pictures represent asymmetric arrangements: ones that we should divide by $3$, because there are $3$ pictures of each arrangement.

So the final answer is $$ 5! + \frac13\left(\frac{15!}{3!^5} - 5!\right) = \frac{15!}{3\cdot 3!^5} + \frac23 \cdot 5! $$ (your original answer is off by $\frac23 \cdot 5! = 80$).

$\endgroup$
1
$\begingroup$

We use the Polya Enumeration Theorem. The cycle index here is

$$Z(G) = \frac{1}{3} a_1^{15} + \frac{2}{3} a_3^5.$$

We then obtain for five colors, three each

$$[A^3 B^3 C^3 D^3 E^3] Z(G; A+B+C+D+E) \\ = [A^3 B^3 C^3 D^3 E^3] \frac{1}{3} (A+B+C+D+E)^{15} \\ + [A^3 B^3 C^3 D^3 E^3] \frac{2}{3} (A^3+B^3+C^3+D^3+E^3)^5 \\ = \frac{1}{3} \frac{15!}{3!^5} + [A B C D E] \frac{2}{3} (A+B+C+D+E)^5 \\ = \frac{1}{3} \frac{15!}{3!^5} + \frac{2}{3} 5! = 56056080.$$

$\endgroup$

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.