Each vertex of a convex pentagon PQRST is to be assigned a color, from an available choice of six distinct colors. The ends of each diagonal must be assigned a different color.
How many different colorings are possible?
A color can be repeated only once, and only if the repeated colors are directly adjacent to each other.
So there are three "types" of color configurations: those with two pairs or the same colors (e.g. blueblueredredgreen), those with one pair of the same color (e.g. blueblueredgreenyellow), and those with no pairs of the same color (e.g. blueredgreenyellowpurple).
Of the first type, there are 6 possible choices for the color of the first pair, 5 possible choices for the color of the second pair, and 4 possible choices for the third solitary color, for a total of 6*5*4 = 120 permutations. Each of these can be positioned in five different ways on the pentagon (e.g. the first pair can start on PQ, or on QR, or RS, etc.), so there are a total of 5*120 = 600 permutations of this type.
Of the second type, there are 6 possible choices for the color of the pair, and then 5, 4, and 3 choices for the remaining colors, respectively. Additionally, there are once again 5 different ways that each of these configurations can be mapped onto the pentagon, so there are a total of 6*5*4*3*5 = 1800 permutations of this type.
Of the third type, there are 6*5*4*3*2 = 720 possible permutations. For this type, we don't need to multiply by 5 because this number already accounts for different positions of the same 5color string (e.g. blueredgreenyellowpurple and redgreenyellowpurpleblue have both already been counted).
So the total number of possible colorings is 600 + 1800 + 720 = 3120.

Posted by tomarken
on 20140718 10:14:56 