Recurrences for tilings part 1

combinatoricscontest-mathrecurrence-relationstiling

The following problems are from chapter 9 of Arthur Engel's Problem solving strategies (questions 60, 61, 62) respectively. For each question, let $a_n$ denote the number of ways for a $k\times n$ board.

  1. In how many ways can you tile a $2\times n$ rectangle by $1\times 1$ squares and L-trominoes?
  2. In how many ways can you tile a $2\times n$ rectangle by $2\times 2$ squares and L-trominoes?
  3. In how many ways can you tile a $3\times n$ rectangle by $2\times 1$ dominoes?

I know some standard approaches for these kinds of problems, but the recurrences I came up with seem to sometimes differ from those given in the solutions.

For instance, for $1$, we have $a_0 = 1, a_1 = 1, a_2 = 5,$ and for $n\ge 3, a_n = a_{n-1} + 4a_{n-2} + 2a_{n-3}$, which follows from considering the following possible shapes at the end of the tiling: a vertical bar of 2 $1\times 1$ squares, a $2\times 2$ square formed from an L-tromino and a 1 by 1 square (there are four ways to do this), and a $2\times 3$ square formed from 2 L-trominoes (there are two possibilities).

For $2, a_1 = 0, a_2 = 1, a_3 = 2, a_4 = 1.$ And we have for $n\ge 5, a_n = a_{n-2} + 2a_{n-3}$ (you can either have a 2 by 2 square or 2 L-trominoes at the end).

For $3$, $a_1 = 0, a_2 = 3, a_3 = 0, $ and for $n\ge 4, a_n = a_{n-2} + 2b_{n-1}$ and $b_n = a_{n-1} + b_{n-2},$ where $b_n$ is the number of ways to tile a $3\times n$ rectangle with one corner square removed. The first recurrence follows since either 3 horizontal 2 by 1 tiles are at the end or one vertical domino and one horizontal one. For the second recurrence, we may assume by symmetry that the removed domino is the top right one. The recurrence follows from the fact that either a vertical domino is at the end or two horizontal dominoes intersect the rightmost two squares and one horizontal domino intersects the square in the second last column. But even though the recurrence is equivalent to the one given in the solutions, I can't seem to figure out how to get the recurrence in that solution directly.

Have I made any mistakes, and if so, what did I do wrong? Also, how can I get the recurrence $a_n = 4a_{n-2} – a_{n-4}$ directly for 3?

Best Answer

Have I made any mistakes, and if so, what did I do wrong?

Your recurrences look fine to me.

Also, how can I get the recurrence $a_n = 4a_{n-2} - a_{n-4}$ directly for 3?

To be honest, I think your recurrence is better, since it's more intuitively obvious / less error-prone. :) But to answer your question, here is one way...

Consider the ways to fill the first $2$ columns (of $3$ squares each). There are $3$ ways to fill them using $3$ complete dominoes. So that accounts for $3a_{n-2}$. Besides these, they can also be filled using $2$ dominoes and $2$ half-dominoes, like this

AA.......
BCC......
BDD......

and its reflection. So we need to argue that the number of ways to fill the remaining ... above (incl. the reflected picture) amount to $a_{n-2} - a_{n-4}$ ways, for the desired total of $a_n = 4a_{n-2} - a_{n-4}$.

Now consider any $3 \times (n-2)$ rectangle, which can be filled in $a_{n-2}$ ways. Consider its first column. Either (case A) there are $3$ half-dominoes (no. of ways $= a_{n-4}$), or (case B) there is a full domino plus a half-domino. So no. of ways for case B $= a_{n-2} - a_{n-4}$, but this is exactly the same as filling the ... in the picture, once you consider C+D to be the full domino in that first column of the $3 \times (n-2)$ rectangle. $\square$

Related Question