I'm trying to solve this problem: In how many ways can you cover a 2xn grid with 1×1, 1×2, 2×1, 2×2 dominos? And here is my attempt: Let a(n) be the number of ways we can cover the grid. Then if we start by putting a 2xn domino first then we have a(n-1) ways to complete the rest of the grid. If we put a 2×2 domino first then we have a(n-2) ways to cover the rest of the grid. If we put a 1×1 domino first (up or down) than we can put either a 1×1 domino or 1×2 domino below (or above) it. If we put the 1×1 domino then we have a(n-1) ways to complete the rest of the grid. Now the problem is when we put the 1×2 domino. I tried to define and find a new recursive relation b(n) for this case of the problem but I am always neglecting some cases. Can anyone help me?
A recursive relation for the number of ways to tile a 2 x n grid with 2×1, 1×2, 1×1 and 2×2 dominos
combinatoricsnumerical methodspolyominorecurrence-relationstiling
Best Answer
Let $b_n$ be the number of tilings of a $2\times n$ board with one corner removed. We define $b_n$ this way because this is the shape that arises when you place a $1\times 1$ and a $1\times 2$ along the left edge of the board.
This gives the following recurrence for $a_{n}$: $$ a_n= \underbrace{a_{n-1}}_{2\times 1}+ \underbrace{a_{n-2}}_{2\times 2}+ \underbrace{a_{n-1}}_{1\times 1\text{ on } 1\times 1}+ \underbrace{b_{n-1}}_{1\times 1\text{ on } 1\times 2}+ \underbrace{b_{n-1}}_{1\times 2\text{ on }1\times 1}+ \underbrace{a_{n-2}}_{1\times 2\text{ on }1\times 2}\qquad (n\ge 2) $$ Now, you just need a recurrence for $b_n$. This is easier, since there are only two cases; either you place a $1\times 1$ in the spot vertically next to the removed corner, or you place a $1\times 2$ there. That is, $$ b_n = b_{n-1}+a_{n-1}\qquad (n\ge 2) $$ Now you need to solve these two mutual recurrences. Note that the first recurrence can be solved for $b_{n-1}$, and then you can substitute that into the second expression to get a recurrence involving $a$ alone.