AMC 12 Mock Exam 3 Problem 25

Let $t_n$ be the number of tilings of a $2\times n$ board, and let $s_n$ be the number of tilings of a $2\times n$ board with one extra cell attached to the right of its top row (by symmetry, the same as with the extra cell on the bottom row). Set $t_0=1$, $s_0=0$.

Recurrence for $s_n$. The protruding cell is covered either by a horizontal domino (leaving a $2\times(n-1)$ board with one protruding cell on the bottom row: $s_{n-1}$ ways) or by an L-tromino that also covers both cells of column $n$ (leaving a $2\times(n-1)$ board: $t_{n-1}$ ways). So $s_n=s_{n-1}+t_{n-1}$.

Recurrence for $t_n$. Look at the last column. Its two cells are covered by a vertical domino ($t_{n-1}$ ways); or by two horizontal dominoes ($t_{n-2}$); or by one L-tromino that covers both of them plus one cell of column $n-1$, which leaves a $2\times(n-2)$ board with a protruding cell ($2s_{n-2}$ ways, for the two orientations). Any other choice leaves a cell of column $n$ that cannot be covered. So $t_n=t_{n-1}+t_{n-2}+2s_{n-2}$.

Computing: $$\begin{array}{c|ccccccccccc} n&0&1&2&3&4&5&6&7&8&9&10\\\hline s_n&0&1&2&4&9&20&44&97&214&472&\\ t_n&1&1&2&5&11&24&53&117&258&569&1255 \end{array}$$ The answer is $\boxed{1255}$. (One can check that $t_n=2t_{n-1}+t_{n-3}$.)