# A recursive relation for the number of ways to tile a 2 x n grid with 2x1, 1x2, 1x1 and 2x2 dominos

I'm trying to solve this problem: In how many ways can you cover a 2xn grid with 1x1, 1x2, 2x1, 2x2 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 2x2 domino first then we have a(n-2) ways to cover the rest of the grid. If we put a 1x1 domino first (up or down) than we can put either a 1x1 domino or 1x2 domino below (or above) it. If we put the 1x1 domino then we have a(n-1) ways to complete the rest of the grid. Now the problem is when we put the 1x2 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?

• My suggestion is to find the first few values of $a(n)$ and then look them up in the OEIS. Commented Nov 15, 2022 at 19:12

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.