In how many ways can the four walls of a room be painted with three colours so that no two adjacent walls have the same colour?

Question

In how many ways can the four walls of a room be painted with three colours so that no two adjacent walls have the same colour ?

---

I specifically want to use inclusion exclusion principle. So according to me it should be $$3^4-4\times 3^3+4\times 3^2-3 $$ which is $6$. The correct answer is $18$. Am making a mistake in applying the principle ? I thought like this - Total ways to colour - ways to colour two adjacent walls with same colour + ways to colour three adjacent walls with same colour - ways to colour all four walls with same colour.

Answer 1

See if we use $3$ colours then any one of the two pairs of opposite should have same colour . now total ways of doing so are. Lets use a colour. Say green is used at $1,3$ wall so we have two ways to use $Red,blue$ colours so for $1$ colour used twice its $2$ ways hence for $3$ its $6$ ways. Again think of green used at wall no $2,4$ so again we have $2$ ways to use $red,blue$ so again these are $6$ ways. So total ways are $12$ now using $2$ colours. Lets use green at $1,3$ so now ways of using red are $1$ and same for blue. So for $1$ colour fixed we can use two 1 out of $2$ colours for remaining walls in two ways ie $GRGR,GBGB$ .( assuming walls are identical) . so total ways where $2$ colours are ised is $6$ hence total ways are $6+6+6=18$

Answer 2

A coloring such as AABB has been subtracted twice: once for the pair AA and once for the pair BB. If you add back all such colorings (3 choices of colors X 2 pairs of opposite walls X 2 ways of coloring = 12), you get the correct answer.

Answer 3

If you insist on using the inclusion exclusion principle you can argue as follows:

Denote the vertical edges of the room by $e_i$ $(1\leq i\leq4)$. There are $3^4$ colorings with no restrictions. There are ${4\choose1}\cdot 3^3$ colorings with at least one illegal edge $e_i$, ${4\choose2}\cdot 3^2$ colorings with at least two illegal edges $e_i$, $e_j$, $i<j$, then ${4\choose3}\cdot3^1$ colorings with at least three illegal edges $e_i$, $e_j$, $e_k$, $i<j<k$, and finally ${4\choose4}\cdot 3$ colorings with all four edges certified illegal. The total number of legal colorings then comes to $$3^4-{4\choose1}\cdot 3^3+{4\choose2}\cdot 3^2-{4\choose3}\cdot3^1+{4\choose4}\cdot 3=18\ .$$