You have six triangles. Two are red, two are blue, and two are green. How many truly different hexagons can you make by combining these triangles?
I have two possible approachtes to solving this question:
-
In general, you can arrange $n$ objects, of which $a$ are of type one, $b$ are of type two, and $c$ are of type three, in $\frac{n!}{a! \cdot b! \cdot c!}$ ways. In this case, $n = 6$, and $a = b = c = 2$. There are 90 possible ways to arrange the six triangles. However, the triangles are in a circle, which means that six different arrangements are really one truly different arrangement. Division by six results in 15 possible hexagons.
-
It is possible to enumerate every different arrangement, and count how many truly different arrangements you can make. There are six different ways to arrange the triangles with the two red triangles next to each other. There are six different ways to arrange the triangles with one triangle between two red triangles. There are four different ways to arrange the triangles with two triangles between two red triangles. This results in 16 possible hexagons. I also wrote a simple computer program that tries every possible combination and counts how many are different, and it confirms the answer 16.
It turns out that the second approach is the right one, and 16 is the right answer. I can enumerate 16 different hexagons that are all different. Now my question is, what is wrong with the first approach? Where is the error?
Remarks:
When you arrange the 16 different hexagons in lines, you can create six different arrangements for each hexagon, but this results in doubles. There are less than 96 different arrangements in a line. This does not contradict the first approach, in which there are no doubles.
Best Answer
You want to count each collection of hexagons interrelated by rotations as a single "truly different" hexagon. If $X$ is the set of hexagons, and $G$ is the group of rotations, then you want to find $|X/G|$: the number of orbits of elements of $X$ under $G$. Burnside's lemma gives the equation for this: $$ |X/G| = \frac{1}{|G|}\sum_{g \in G}|X^{g}| = \frac{|X|}{|G|} + \frac{1}{|G|}\sum_{g \in G | g \neq e}|X^g|, $$ where $X^g$ is the set of elements fixed by $g$, and the second sum excludes the identity element of $G$. In this case, you correctly counted $|G|=6$ and $|X|=90$, and so if no hexagons were fixed by a non-zero rotation, then $90/6=15$ would be the right answer. However, there are $6$ hexagons fixed by the $180^{\circ}$ rotation, giving an additional contribution of $6/6=1$, for a total of $15+1=16$.