Tiling a $2\times 6$ grid

Question

Find the number of ways to tile a $2 \times 6$ grid board with the following 2 types of dominoes - (i) A $2×1$ black dominoes (ii) A $2×2$ red dominoes

Here's how i though of this - It is trivial to see a tiling $2×2$ domino can also be done using $2$ $2×1$ dominoes, and number of $2×1$ dominoes must be even on either row or the column of the board (as on the contrary we caannot tile using 2×2$).

I need help after this thanks!

Answer 1

Let $f(n)$ represent the number of ways to tile a $2\times n$ grid. If $n$ is sufficiently large, the right hand column can be filled in one of three ways.

• If there is a vertical black domino, then the rest of the grid can be filled in $f(n-1)$ ways.
• If there are two horizontal black dominoes tiling the right column and the one next to it, then the rest of the grid can be filled in $f(n-2)$ ways.
• If there is a red $2\times 2$ tertromino, then the remainder of the grid can be filled in $f(n-2)$ ways.

Therefore, if $n\ge2$, we have $f(n)=f(n-1)+2f(n-2)$. Adding in that $f(0)=f(1)=1$, we can calculate out that $f(6)=43$.