Number of ways to color in a $2\times5$ grid

Question

How many ways are there to color in each unit square of a $2\times5$ grid red or blue so that no $2\times2$ square is allowed to be the same color?

So I thought about doing an inclusion-exclusion method to approach this problem, but my main issue with this approach was that it was too hard to bash out all the cases involved with such an approach (that is, considering the cases where there exist $2\times2$ squares which are the same color). Any thoughts on a better approach I could take?

Answer 1

Let $a_n$ denote the number of good colorings of a $2\times n$ grid. You want to compute $a_5$. The initial conditions are $a_0 = 1$ and $a_1 = 4$. To derive a recurrence relation for $a_n$, consider the four possibilities for the two cells in the leftmost column. You will find that $a_n = 3 a_{n-1} + 2 a_{n-2}$, yielding: \begin{align} a_2 &= 3 a_1 + 2 a_0 = 3\cdot4 +2\cdot 1 = 14 \\ a_3 &= 3 a_2 + 2 a_1 = 3\cdot14 +2\cdot 4 = 50 \\ a_4 &= 3 a_3 + 2 a_2 = 3\cdot50 +2\cdot 14 = 178 \\ a_5 &= 3 a_4 + 2 a_3 = 3\cdot178 +2\cdot 50 = \color{red}{634} \end{align}

---

Alternatively, if you just care about $n=5$, the inclusion-exclusion approach yields \begin{align} a_5 &= 2^{10} - 2(5-1)2^6 + (2(5-2)2^4 + 2^2\cdot 3\cdot 2^2) - (2(5-3)2^2 + 2^3\cdot 2^0) + 2(5-4)2^0 \\ &= 1024 - 512 + (96 + 48) - (16 + 8) + 2 \\ &= \color{red}{634} \end{align}

Answer 2

Thanks for explaining how you came to the recurrence relation $a_n = 3a_{n-1}+2a_{n-2}$, Rob. Here's a potentially more direct way.

We want to build all the allowed $2 \times n$ grids from shorter grids. For each allowed $2 \times (n-1)$ grid, suppose the rightmost column is $x \atop z$ where $x, z \in \{b,r\}$ could be the same or different. Let $y \ne x$, i.e., $y$ and $x$ are different colors. We can make an allowed $2 \times n$ grid by appending each of the three columns $x \atop y$, $y \atop x$, and $y \atop y$, which gives the $3a_{n-1}$ term in the recurrence.

What $2 \times n$ grids are missing from that construction? The ones whose last two columns have the form ${x \, x} \atop {z \,x}$ with $x \ne z$, that is, ${b \, b} \atop {r \, b}$ or ${r \, r} \atop {b \, r}$. Append each of those $2 \times 2$ blocks to each allowed $2 \times (n-2)$ grid. These complete the $2 \times n$ grids, do not overlap with the ones built from $2 \times (n-1)$ grids, and account for the $2a_{n-2}$ term in the recurrence.