[Math] Calculate how many ways can you paint the corners of a Pentagon

combinatorics

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)}

Best Answer

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.

Related Question