\documentstyle[12pt]{article}
\pagestyle{empty}
\begin{document}
\begin{center}
Math 192r, Problem Set \#6: Solutions \\
\end{center}
\medskip
\begin{enumerate}
\item
{\it For each even integer $n \geq 2$,
we can represent each domino tiling of a 3-by-$n$ rectangle
by a codeword $(a_1,a_2,\dots,a_n)$,
where $a_k$ is the number of vertical dominos
in the $k$th column (always either 0 or 1).
Note that two different tilings can have the same codeword;
e.g., for $n=2$
there are three tilings but only two codewords
(namely $(0,0)$ and $(1,1)$).
Formulate a conjecture for the number of codewords
that occur for general $n$.}

Here is some Maple code that does quite a lot:
\begin{verbatim}
with(linalg):
m :=proc(k) matrix(3,3,
        [1+2*x(k),x(k),x(k),y(k),1,0,y(k),0,1]); end;
count := proc(n) nops(expand(multiply(
        seq(m(i),i=1..n))[1,1])); end;
\end{verbatim}

The first line tells Maple to use the linear algebra package
{\tt{linalg}}.
The second line tells Maple to define 
{\tt{m(}}$n${\tt{)}} as the 3-by-3 matrix
$$\left( \begin{array}{ccc}
1+2x(k) & x(k) & x(k) \\
y(k) & 1 & 0 \\
y(k) & 0 & 1 \end{array} \right). $$
The third line tells Maple that when it receives the command
{\tt{count(}}$n${\tt{)}}, 
it should take the product of $n$ such 3-by-3 matrices,
look at the upper left entry in the product,
expand it out,
and count the number of operands (that is,
count the number of terms in the expansion).

This calls out for some explanation.
Suppose we assign weight $x(k)$ (resp.\ $y(k)$)
to either of the two vertical dominos
occurring in the $2k-1$st (resp.\ $2k$th) column
of a 3-by-$n$ rectangle,
and suppose we assign to each tiling of this rectangle
a weight equal to the products of the weights
of the constituent vertical tiles.
Then it is clear that the weight of a tiling
determines its codeword, and vice versa,
with the presence or absence of the weight $x(k)$ or $y(k)$
indicating the occurrence of a 1 or a 0
at the corresponding location in the codeword.
So we can count the distinct codewords
by counting the number of terms in the polynomial
that is obtained by summing the weights of all the tilings.

We can do this using a 3-by-3 transfer matrix
to handle three mutually recursive sequences simultaneously:
the first counts domino tilings of a 3-by-$2n$ rectangle,
the second counts domino tilings of a 3-by-$2n+1$ rectangle
with a bite taken out of the upper right corner,
and the third counts domino tilings of a 3-by-$2n+1$ rectangle
with a bite taken out of the lower right corner,
(There is some redundancy here between
the second and third sequence,
but it's simpler conceptually, if not computationally,
to keep it around.)

Another approach is to generate all the tilings,
determine their codewords, and strip out redundancies,
using the fact that when Maple takes a union of two sets,
it takes care of removing duplicates for you
(provided you've represented objects in such a way
that Maple's notion of equality
coincides with yours).

Under either approach, one finds that
the number of codes of domino tilings of a 3-by-$2n$ rectangle
appears to equal the number of domino tilings of a 2-by-$2n$ rectangle.
It should also be noted that all the polynomials
obtained from the Maple code given above
have coefficients that are powers of 2.
That is, for each codeword,
the number of tilings of the 3-by-$2n$ rectangle that
have that particular codeword
always seems to be a power of 2.

\item
{\it Let $a_n$ be the number of domino tilings
of a 4-by-$n$ rectangle, with $n \geq 0$
(we put $a_0 = 1$ by convention).}
\begin{itemize}
\item[(a)] {\it Prove that the sequence $a_0,a_1,\dots$
satisfies a linear recurrence relation of order 16 or less.}

For each vertical line through the tiling
that divides one column of height 4 from the next,
there are $2^4=16$ different ways in which
one might see 0 to 4 horizontal dominos
being pierced by the line.
If we give each of these 16 patterns a symbol,
then every domino tiling of a 4-by-$n$ rectangle
is represented by a string of $n+1$ symbols
from an alphabet of size 16,
beginning and ending with the symbol that means
``no horizontal dominos pierced by this line''
(corresponding to the left end and right end of the rectangle);
call this the first symbol.
Conversely, such a codeword corresponds to exactly one tiling
if certain forbidden adjancies do not occur,
and otherwise corresponds to no tilings at all.
Thus the number of (domino-)tilings of the 4-by-$n$ rectangle
is equal to the upper-left entry of the $n$th power
of the 16-by-16 matrix whose $i,j$th entry
tells whether the $i$th symbol can occur
next to the $j$th symbol.
By the Cayley-Hamilton theorem,
the sequence consisting of these entries
must satisfy the 16th-order linear recurrence relation
given by the characteristic polynomial of the matrix.

\item[(b)] Prove that the sequence $a_0,a_1,\dots$
satisfies a linear recurrence relation of order 8 or less.

To prove this claim,
it's enough to show that half of the 16 symbols
cannot occur in such a codeword
(so that the 16-by-16 matrix can be replaced by an 8-by-8 matrix).
To see this, note that half of the symbols indicate the presence
of an odd number of horizontal dominos
being pierced by a particular vertical line.
That is, if you divide the rectangle in half along the vertical line
and remove the horizontal dominos that the line pierces,
one is left with two sub-regions, each with odd area.
But then these two sub-regions cannot be tiled by dominos
(since a domino has even area).
Hence only 8 of the 16 symbols can occur
in codewords of the form $(1,\dots,1)$,
and the claim is proved.

\item[(c)] Prove that the sequence $a_0,a_1,\dots$
satisfies a linear recurrence relation of order 6 or less.

Now we show that only 6 of the original 16 symbols
can actually participate in a codeword of the form $(1,\dots,1)$.
Color the constituent squares of the rectangle black and white.
If we have a tiling of the rectangle
and we cut it along a vertical line (discarding the bisected pieces),
the two remaining regions must be tilable by dominos;
so each must contain as many black squares as it contains white squares.
On the other hand, suppose we bisect the rectangle along the same line
and {\it don't\/} discard the bisected pieces;
then (since each column has an even number of squares)
it's clear that each side must contain as many black squares as white.
It follows that, among the bisected dominos,
there must be as many 
with a black square on the left and a white square on the right
as there are
with a white square on the left and a black square on the right.
This leaves only six possibilities:
no bisected dominos;
bisected dominos in rows 1 and 2;
bisected dominos in rows 1 and 4;
bisected dominos in rows 3 and 2;
bisected dominos in rows 3 and 4;
and bisected dominos in all four rows.

\end{itemize}

\end{enumerate}

\end{document}

