Q:

How many ways are there to color the walls of a pentagonal room using five different colors, so that no two non-adjacent walls have the same color?

How many ways are there to color the walls of a pentagonal room using five different colors, so that no two non-adjacent walls have the same color?

I tried casework, but it got very messy before long. I can't think of any other way to approach the problem. Can anyone help?
Thanks!

A:

I actually answered the question:”How many colorations of a the pentagonal room are there such that two adjacents wall never have the same colour?”, but apparently in this particular case the two problems are equivalent.
You can try "recursevely". Let's call $C_n$ the number of suitable colorations for an $n$-gon. Now let's consider your pentagon , imagine to colour only four sides. You can for sure colour them as if they were the sides of a square(imagine to remove "the excluded side" and to glue together the 2 unconnected sides):so at least in $C_4$ ways.In this scenario you can colour the last side in $3$ ways(since we coloured the other four sides as if it was a square, the adjacent sides of the "excluded side" are of different colours). This means that:
$$C_5>3C_4$$
Now we have to consider the cases in which the two "unconnected sides" are of the same colour($5 $possibilities). Than the excluded side can be coloured in $4$ ways and the remaining two sides have to be of different colours(since they are adjacent) and of different colour from the colour of the two "unconnected sides". That is to say $4*3=12$ possibilities. In total $5*4*12=240$. So:
$C_5=3C_4+240$
Now you can brute force calculate $C_4$ or apply the same reasoning:
$C_4=3C_3+80$
Notice that $C_3=5*4*3=60$ since we have to choose a different colour for each side. It follows that:
$$C_4=260$$
$$C_5=1020$$

