3
$\begingroup$

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?

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

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Nice. I'm curious how much faster does this grow compared to the fibonacci numbers. $\endgroup$ Commented Nov 15, 2022 at 20:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .