Number of ways to colour a $2×N$ grid

Question

You have to colour a grid map. You will be given a $2×N$ ($2$ rows and $N$ columns) grid where each cell represents a country. The grid map can be coloured using at most $K$ different colours. But no two cells sharing a common side will have same colour. How many different grid maps can you produce?

Answer 1

We colour the grid one column at a time, starting at the left. For the first column, disregarding the adjacency rule, there are $K^2$ ways to colour it, but $K$ of those ways have adjacent cells the same colour and are thus disallowed. Hence the first column can be coloured in $K^2-K=K(K-1)$ ways.

For the remaining $N-1$ columns, look at the following picture:

A1
B2

Given that A and B are fixed and different colours in the last column coloured, there are $K-1$ possible colours for cell 1, disregarding what colour cell 2 is. The same number holds for cell 2, disregarding cell 1. But of the ways to colour cells 1 and 2 that follow, $K-2$ ways have them the same colour and are hence disallowed. Hence given a coloured column on the left there are $(K-1)(K-1)-(K-2)=K^2-3K+3$ ways to colour the next column.

Multiplying, we find that there are $K(K-1)(K^2-3K+3)^{N-1}$ ways to colour the $2×N$ grid.