Lesson 10

Initially, before the first column, the profile is empty: \[w_{0}=\begin{pmatrix}1&0&0&0\end{pmatrix}.\] After \(n\) columns, the vector is \(w_{0}M^{n}\). A complete tiling of the \(3 \times n\) rectangle must also end with the empty profile \(\texttt{000}\). Hence \(T(n)\) is the first coordinate of \(w_{0}M^{n}\).

The determinant gives \[\det(I-xM)=1-4x^{2}+x^{4}.\] Therefore \[T(n)=4T(n-2)-T(n-4).\] The first values are \[T(0)=1,\quad T(2)=3,\quad T(4)=11,\quad T(6)=41,\quad T(8)=153.\] Notice also that \(T(n)=0\) for odd \(n\), since a \(3 \times n\) rectangle then has an odd number of cells.