If the walls of a hexagon shaped room are to be painted so that no two adjacent walls get painted the same colour, and there are 10 colours of paint to be chosen from, how many ways can the room be painted?
I believe it is to be assumed that rotations of the hexagon should be counted as distinct colourings. So far, I've managed to split the problem up into cases:
- The hexagon is painted with k=6 colours chosen from the 10 colours
- The hexagon is painted with k=5 colours and one repeated colour
- The hexagon is painted with k=4 colours where two colours appear twice
- The hexagon is painted with k=3 colours where three colours appear twice
- The hexagon is painted with k=2 colours where the two colours appear 3 times
Obviously the hexagon cannot be painted with one colour. I imagine the Principle of Inclusion/Exclusion may be helpful here. From here, I'm not exactly sure on how to turn these cases into numbers, or if my cases are correct. Thanks very much in advance!
HINT only. And I also assume reflections are considered distinct (just as rotations are distinct).
Sequences of walls are easy to analyze than loops, because you don't have to worry about the last wall matching up with the first wall. If you color a sequence of $N$ walls with $M$ colors and require adjacent walls to be different colored, then simply start from one end with any color, then for each subsequent wall use a color which is different from the previous. This immediately gives $M \times (M-1)^{N-1}$.
Since rotations are distinct, first make a dent in one of the walls. This dented wall can be colored in $10$ ways. Then condition on if and where this color is re-used.
If this color is not used again, the remaining sequence of $5$ walls can be colored in $9\times 8^4$ ways.
If this color is used again twice, then ...
If this color is used again once, then it can be on the 3rd, 4th or 5th walls (counting clockwise from the dented wall, with the dented wall as 1st). The numbers in those three cases are respectively ...
Can you finish from here?