\documentstyle[12pt]{article}
\pagestyle{empty}
\begin{document}
\begin{center}
Math 491, Problem Set \#11 (Solutions)
\end{center}
\medskip
\begin{enumerate}
\item
{\it Let $c_n$ be the number of domino tilings
of a 3-by-$2n$ cylinder,
obtained by gluing together the left and right sides (of length 3)
of a 3-by-$2n$ rectangle.
Express the generating function
$c_1 x + c_2 x^2 + c_3 x^3 + \dots$
as a rational function of $x$.}
Where two squares meet side by side,
record a 0 if they are covered by a single (horizontal) domino
and a 1 otherwise.
Then there are eight possible patterns of 0's and 1's
as one reads down,
which we treat as numbers between 0 through 7
via binary encoding.
Then the domino tilings of the 3-by-$2n$ cylinder
correspond to circular words of length $2n$
in the symbols 0 through 7,
where the allowed transitions are summarized
in the following matrix
(with rows and columns indexed consecutively
from 0 through 7):
\[ M = \left( \begin{array}{cccccccc}
0&1&0&0&0&0&0&0\\
0&0&0&0&0&0&1&0\\
0&0&0&0&0&1&0&0\\
0&0&0&0&1&0&0&1\\
0&0&0&1&0&0&0&0\\
0&0&1&0&0&0&0&0\\
0&1&0&0&0&0&0&1\\
1&1&0&0&1&0&0&0
\end{array} \right) \]
That is, in Maple-ese,
\begin{verbatim}
M := matrix(8,8,[
0,1,0,0,0,0,0,0,
0,0,0,0,0,0,1,0,
0,0,0,0,0,1,0,0,
0,0,0,0,1,0,0,1,
0,0,0,1,0,0,0,0,
0,0,1,0,0,0,0,0,
0,1,0,0,0,0,0,1,
1,1,0,0,1,0,0,0]);
\end{verbatim}
Maple, in response to the command
{\tt charpoly(M,t)},
tells us that the characteristic polynomial
of this matrix is
$\det(tI-M) =
t^8-3t^6-2t^5+2t^4+4t^3+t^2-2t-1$,
so the twisted version is
$Q(x) = \det(I-xM) =
1-3x^2-2x^3+2x^4+4x^5+x^6-2x^7-x^8$,
which factors as $(1-x)^2 (1+x)^2 (1-x-x^2) (1+x+x^2)$.
Therefore
$\frac{-xQ'(x)}{Q(x)} =
\frac{2x(1-x)}{(1-x)^2} - \frac{2x(1+x)}{(1+x)^2}
+ \frac{x+2x^2}{1-x-x^2} + \frac{-x-2x^2}{1+x+x^2} =
\frac{6x^2+6x^3-2x^4-14x^5-8x^6}{(1-x)(1+x)(1-x-x^2)(1+x+x^2)}$.
\end{enumerate}
\end{document}