Problem
COM-B1-M10-P024 Dominoes and L-Trominoes
A \(2\times6\) board is tiled by dominoes and L-trominoes. Find the number of tilings.
Introduce two states: a full board and a board with one right corner missing.
Let \(A_n\) be the number of full tilings of \(2\times n\), and let \(B_n\) be the number of tilings of a \(2\times n\) board with one right corner cell removed. Then \(B_n=A_{n-2}+B_{n-1}\): the gap can be closed by an L-tromino, leaving a full rectangle of width \(n-2\), or the gap state can be shifted one column. For the full board, \(A_n=A_{n-1}+A_{n-2}+2B_{n-1}\): the last block is a vertical domino, two horizontal dominoes, or two symmetric ways to close the right part using a gap state. Initial values: \(A_0=1\), \(A_1=1\), \(B_0=0\), \(B_1=0\). We get \(B_2=1\), \(A_2=2\); \(B_3=2\), \(A_3=5\); \(B_4=4\), \(A_4=11\); \(B_5=9\), \(A_5=24\); \(B_6=20\), \(A_6=53\). Answer: \(53\).
Strong problem on extra states; this is genuine dynamic programming.