Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:

  1. 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.

  2. 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.

share|improve this question
    
You are counting reflections as distinct. Often (not always) when counting rotations together then reflections are lumped in, too. –  Ross Millikan Feb 10 '11 at 16:54
    
Yes, in this case two hexagons that can be rotated to the same hexagon are considered equal, but two hexagons that can be mirrored to the same hexagon are not. –  Ruud v A Feb 10 '11 at 17:28

3 Answers 3

up vote 2 down vote accepted

The problem in approach 1 is your assumption that every arrangement has 6 distinguishable rotations of that arrangement. This is not true, because some arrangements are preserved by a one-half rotation of 180 degrees. (We should also check for any arrangements preserved by a one-third rotation of 120 degrees, but there aren't any of those.)

What permutations are preserved by a half-turn? RGBRGB (identified with GBRGBR and BRGBRG) and RBGRBG (identified with BGRBGR and GRBGRB). So, among the 90 total permutations, we have 84 that come from 14 possibilities times the 6 rotations and 6 that come from 2 possibilities times the 3 rotations.

share|improve this answer
1  
As you noted, the total number of permutations is (6 choose 2,2,2) = 90. The total number of permutations preserved by a half rotation is (3 choose 1,1,1) = 6. But we know each of these shows up 3 times, so there are only 2 truly different arrangements. –  Jonas Kibelbek Feb 10 '11 at 16:56

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$.

share|improve this answer

enter image description here

share|improve this answer
    
This does not answer the question. –  Ruud v A Feb 16 '11 at 11:11
    
I know, but aren't they pretty? –  I. J. Kennedy Feb 16 '11 at 19:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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