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.

I'm studiying for an exam I have on combinatorics next week and I'm stuck with the solution to this question:

Imagine you have a pentagon and you want to color the corners of the pentagon so that no two adjacent corners have the same color. If you have 'q' colors, how many ways of coloring the pentagon are possible.

I say that the answer is $q^2*(q-1)^2*(q-2) + q*(q-1)*(q-2)^2*(q-3)$.

My friend says the answer is $MyAnswer + q*(q-1)*(q-2)*(q-3)*(q-4)$.

Who is right? (or are we both wrong).

Further if you could point out a resource that explains how to calculate this question for other numbers of corners (say an hexagon) we would really appreciate it.

EDIT:

Answering to some comments in the answer, rotations of the pentagon should not be counted. What I mean is that if we have 5 colors (a,b,c,d,e) the pentagon with corners {(1,a),(2,b),(3,c),(4,d),(5,e)} is exactly the same as {(1,c),(2,d),(3,e),(4,a),(5,b)}

share|improve this question
    
Your friend is computing the way of assigning five different colors, in order, to the vertices; this is incorrect, since you can have repeated colors. I don't understand how you are doing things. Neither of you seem to be taking into account symmetry (will two colorings that can be obtained from one another by rotating the pentagon be considered the same?). If we do not take consider rotation-equivalent colorings as the same, I get $2q(q-1)^2(q-2) + q(q-1)(q-2)^2$ possible colorings, depending on whether vertices $1$, $2$ and $4$ are colored with just two colors, or if we use three for them. –  Arturo Magidin Oct 10 '10 at 21:57
add comment

2 Answers 2

up vote 5 down vote accepted

Here I am going to assume that we are not looking for distinct configurations, that is, we count a rotation or reflection of the pentagon to be a distinct possibility.

You both have incorrect terms. Consider having only $3$ colors, ie $q = 3$. In this condition there must be a vertex which lies between two points which have the same color. There are $3 \times 2 = 6$ ways to color these three points, leaving $2$ ways to color the remaining two points for a total of $12$ possibilities. But $3^2 \times 2^2 \times 1 + 0 + (0) = 36$, which is too many.

Hint: If you are coloring a pentagon, there are three possible cases:

  1. The pentagon can be colored with $k = 5$ distinct colors chosen from the $q$ possibilities.

  2. The pentagon can be colored with $k = 4$ distinct colors and one repeat.

  3. The pentagon can be colored with $k = 3$ distinct colors where two colors appear twice. (We also have that one color could appear three times, but then it would be impossible to color a pentagon without the same color being adjacent.)

It is easy to see that it is impossible to color the vertices of a pentagon with only 2 colors such that the same color is not adjacent anywhere.

In your question, your friend is accounting for the $q(q-1)(q-2)(q-3)(q-4)$ ways to color a pentagon using $5$ distinct colors. To find the final solution, we need to count how many ways we can color a pentagon in each of the given cases and then we sum all the possibilities together.

Now, for each of the three cases, $q$ choose $k$ to fix the k elements you are working with, then consider how many ways you can color a pentagon using those $k$ colors.

Any more assistance will be moving towards an outright solution so I believe I should stop here.

share|improve this answer
    
Thanks, great answer! I think that you just gave us the outright solution (you just didn't write it). We appreciate it a lot!! –  Carlos G. Oct 11 '10 at 1:41
add comment

You need to specify the problem better. Do you count rotations and reflections as different? For example, imagine a regular pentagon drawn on a sheet of paper with a corner up. Starting from the top corner and going clockwise, maybe we have 0,1,2,3,4 (using numbers instead of colors). Is this different from 1,2,3,4,0? How about from 0,4,3,2,1?

The easiest situation is if you say these are all different. Then the naive approach would be to say you have $q$ choices for the top corner, $q-1$ choices for each of the next three corners (as you can't have neighboring corners that match) and $q-2$ choices for the last, giving $q*(q-1)^3*(q-2)$, but this ignores the fact that the first and fourth corners could be the same color, giving $q-1$ choices for the last.

One way to deal with this situation is to separate into classes based on which corners match the top one. If we designate the top corner 0 and count clockwise, you can match the top color only in no corner, corner 2, or corner 3. So matching none, we have $q*(q-1)*(q-2)^3 $ as at corner 1 you can use any color but the color at corner 0, but for each other you have two eliminated. Matching corner 2, we have $q*(q-1)*1*(q-1)*(q-2)$ and matching corner 3 we have $q*(q-1)*(q-1)*1*(q-2)$. Add them all up and you have your answer.

In general, the answer has to be a fifth degree polynomial. For large $q$ the constraint of not matching colors won't reduce the count very much. So if you count the solutions for six different q (I suggest 0 through 5), you can fit a fifth degree polynomial through them.

If you want to count rotations and reflections as the same there are two possibilites. One way is to define a standard position and only count those cases in standard position. In this case this is easy. You would say that the smallest number has to be at the top, and that corner 2 is less than corner 3. A pitfall would be to say the smallest is at the top and corner 1 is less than corner 4. It could be that corner 1 and 4 are the same, and it could be that one of corner 2 and 3 is the same as corner 0. But counting how many configurations satisfy this constraint may not be easy. It is again a fifth degree polynomial. The other case is to list the configurations of matching corners and see how many times they each get counted. So if no corners match there are $q*(q-1)*(q-2)*(q-3)*(q-4)$ possibilities, but you have counted each one 10 times, so divide these by 10. Then you can have one pair or two pair of corners matching. These are probably easier to count by the standard position approach. If one pair matches, say they have to be positions 0 and 2. So we have $q*(q-1)*1*(q-1)*(q-2)$ choices for this. And so on.

Sorry for taking out the asterisks from my expressions, but it rendered in italics and run over itself when they were there. I think they made it easier to read.

share|improve this answer
2  
You can escape the asterisks with backslashes and they'll work properly in your math. I just found this out today. –  Paul VanKoughnett Oct 10 '10 at 22:24
    
Thanks. I have put them back in. –  Ross Millikan Oct 10 '10 at 22:29
add comment

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.