Lesson 9

Here is a more interesting example. Let \(T(n)\) be the number of ways to tile a \(3 \times n\) rectangle with dominoes of size \(1 \times 2\).

For example, here is one possible tiling of a \(3 \times 8\) rectangle:

We scan the rectangle from left to right. At any moment, some cells in the next column may already be occupied by horizontal dominoes started in the previous column. Such a pattern is called a profile. Since the height is \(3\), a profile can be encoded by a binary string of length \(3\).

By symmetry, it is enough to keep four types of profiles: \[\texttt{000},\quad \{\texttt{001},\texttt{100}\},\quad \{\texttt{011},\texttt{110}\},\quad \texttt{111}.\] The two remaining profiles, \(\texttt{010}\) and \(\texttt{101}\), do exist, but they are not reachable from \(\texttt{000}\).

If the state vector is ordered as above, then one column is transferred by the matrix \[M= \begin{pmatrix}0&2&0&1\\ 1&0&1&0\\ 0&1&0&0\\ 1&0&0&0\end{pmatrix}.\]