1
$\begingroup$

I want to solve to following two-part problem. I solved the first part but I am not sure how to start on part B.

A) How many ways are there to color the 6 vertices of a regular hexagon using 4 colors ?

My answer is 430, which I am pretty sure about.

B) The 4 colors are red, blue, green, yellow. You are only allowed to use (at max): red and blue twice, green and yellow once - How many ways can you color the hexagon now?

This should result in far less possible solutions, but I am not sure how I can solve this problem.

$\endgroup$
  • $\begingroup$ Shouldn't the answer to $A$ be $4^6$? Or should colurings be considered the same if they can be obtained by rotation/reflection from each other? $\endgroup$ – Hagen von Eitzen May 10 '15 at 12:43
  • $\begingroup$ The number $6$ is very small. For B) the at max is irrelevant, we have to use $1$ green, $1$ yellow, and $2$ each of the others. The answer depends on whether if one colouring is obtained by rotation from another, the colourings are viewed as being the same. If they are, we can assume the green vertex is determined. Quickly we get $(5)\binom{4}{2}$. If colourings that are obtained from each other are considered the same, again we can count quite easily, without group-theoretic machinery. $\endgroup$ – André Nicolas May 10 '15 at 12:43
  • $\begingroup$ In part A, including rotation and reflections does give you 430. $\endgroup$ – Josh B. May 10 '15 at 12:44
  • 1
    $\begingroup$ Yeah sorry I should have added that we indeed include rotation and reflection. $\endgroup$ – Carnivean May 10 '15 at 12:49
  • $\begingroup$ In my comment above, in the last sentence it should be "$\dots$ from each other by reflection $\dots$" $\endgroup$ – André Nicolas May 10 '15 at 12:55
1
$\begingroup$

As mentioned in the comments you are using exactly $2$ red, $2$ blue, $1$ green, and $1$ yellow vertices.

To find the number of colorings including rotation and reflection we use Burnside's Lemma. We need to count how many colorings are fixed under the various symmetries of the Hexagon. Since we only have $1$ green vertex, any symmetry which fixes a coloring must also fix a vertex of the hexagon. This reduces the cases we must check.

For the colorings fixed by the identity: $6$ choices for green, $5$ remaining choices for yellow, and then $\binom{4}{2}$ choices for red, and blue is determined giving a total of $180.$

The only other symmetries which fix a vertex are the $3$ reflections over the a line which goes through two opposite vertices. For a coloring to be fixed under this reflection the two fixed vertices must be green and yellow and the two pairs of reflected vertices must be red and blue. This gives $2\times2=4$ colorings fixed under each of these $3$ reflections.

Now we add up and divide by the size of the symmetry group.

$\frac{180+3\times4}{12}=16$ colorings.

$\endgroup$
  • 1
    $\begingroup$ Thanks for nice write up. I am currently trying to get used to the Burnside Lemma, but I am not that comfortable with it yet, so thanks for the detailed walkthrough, it helps a lot. $\endgroup$ – Carnivean May 10 '15 at 13:19

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.