\documentclass[12pt]{article}
\begin{document}
\begin{center}
Math 491, Problem Set \#10 (Solutions)\\
\end{center}
\medskip
\begin{enumerate}
\item
\begin{itemize}
\item[(a)]
{\it Use transfer matrices to find the generating function for the number of
domino-tilings of the 4-by-$n$ grid-graph.}
We can represent each tiling by a word of length $n+1$, whose $i$th symbol
tells us which rows of the tiling contain horizontal dominos in the $i-1$st
and $i$th columns. (Here we count the leftmost column as the first.)
Specifically, we can use the letters N, T, M, B,
O, and A so signify that there are No horizontal dominos spanning those
two columns, or two in the Top two rows, or two in the Middle two rows,
or two in the Bottom two rows, or two in the Outer two rows, or two in All
four rows. Our transfer matrix then looks like
\[
M = \left(
\begin{array}{cccccc}
1&1&0&1&1&1\\
1&0&0&1&0&0\\
0&0&0&0&1&0\\
1&1&0&0&0&0\\
1&0&1&0&0&0\\
1&0&0&0&0&0
\end{array} \right)
\]
(Here rows and columns correspond to the symbols N, T, M, B, O, and A,
in that order.) We are interested in words of length $n+1$ that begin and end
with the symbol N, corresponding to the fact that no domino is permitted to
span the zeroeth and first columns nor the $n$th and $n+1$st boundary, since
in both cases such a boundary would partly fall outside the region being tiled;
that is, we are interested in the upper-left entry of the $n$th power of $M$:
\[
M^2 = \left(
\begin{array}{cccccc}
{\bf 5}&2&1&2&1&1\\
2&2&0&1&1&1\\
1&0&1&0&0&0\\
2&1&0&2&1&1 \\
1&1&0&1&2&1\\
1&1&0&1&1&1
\end{array}
\right),
M^3 = \left(
\begin{array}{cccccc}
{\bf 11}&7&1&7&6&5\\
7&3&1&4&2&2\\
1&1&0&1&2&1\\
7&4&1&3&2&2 \\
6&2&2&2&1&1\\
5&2&1&2&1&1
\end{array}
\right),
\]
etc.
The characteristic polynomial of $M$ is $t^6-t^5-6t^4+6t^2+t-1$,
so the sequence whose $n$th term is the number of domino tilings
of the 2-by-$n$ rectangle (call this number $a_n$)
satisfies the recurrence
$a_{n+6}-a_{n+5}-6a_{n+4}+6a_{n+2}+a_{n+1}-a_{n}$.
So, to reconstruct the sequence,
it suffices to know any six consecutive terms and
then apply the recurrence.
We already know from the preceding paragraph
that $a_1=1$, $a_2=5$, and $a_3=11$.
We could find $a_4$ through $a_6$ by raising $M$
to the 4th, 5th, and 6th powers respectively
(and taking the upper left entries of these matrices),
but here's another way:
Since the matrix $M$ is non-singular,
we can multiply the relation $M^6-M^5-6M^4+6M^2+M-I=0$
by any positive or negative power of $M$,
and by taking the upper-left-hand entry of
the resulting equation,
we find that if we extend the definition of $a_n$ for $n \leq 0$
to be the upper left entry of $M^n$,
the $a$-sequence satisfies the aforementioned recurrence relation
for {\it all\/} integer values of $n$ (not just positive ones).
We already know that
\[
M^0 = I = \left(
\begin{array}{cccccc}
{\bf 1} & 0 & 0 & 0 & 0 & 1\\
0 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 1
\end{array} \right) .
\]
Using Maple (or working by hand), it is not hard to compute that
\[
M^{-1} = \left(
\begin{array}{rrrrrr}
{\bf 0} & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 1 & 0 & -1\\
0 & 0 & 0 & 0 & 1 & -1\\
0 & 1 & 0 & 0 & 0 & -1\\
0 & 0 & 1 & 0 & 0 & 0\\
1 & -1 & -1 & -1 & 0 & 1
\end{array}
\right)
\]
whence
\[
M^{-2} = (M^{-1}) (M^{-1}) \left(
\begin{array}{rrrrrr}
{\bf 1} & -1 & -1 & -1 & 0 & 1\\
-1 & 2 & 1 & 1 & 0 & -2\\
-1 & 1 & 2 & 1 & 0 & -1\\
-1 & 1 & 1 & 2 & 0 & -2\\
0 & 0 & 0 & 0 & 1 & -1\\
1 & -2 & -1 & -2 & -1 & 5
\end{array}
\right).
\]
Therefore the sequence of $a_n$'s, commencing with $a_{-2}$,
begins $1,0,1,$
%kludge
$1,5,11$, and (by the recurrence relation) continues
$36,95,281,781,\dots$.
We know that the generating function for the $a_n$'s,
when multiplied by the denominator $1-x-6x^2+6x^4+x^5-x^6$
must give a polynomial of degree at most 5.
Multiplying $1+x+5x^2+11x^3+36x^4+95x^5+281x^6+781x^7+\dots$
by $1-x-6x^2+6x^4+x^5-x^6$, we get $1-2x^2+x^4$.
Hence
\begin{eqnarray*}
A(x) & = & \sum_{n=0}^{\infty} a_n x^n =
\frac{1-2x^2+x^4}{1-x-6x^2+6x^4+x^5-x^6}\\
& = &\frac{(1-x^2)^2}{(1-x^2)(1-x-5x^2-x^3+x^4)}\\
& = &\frac{1-x^2}{1-x-5x^2-x^3+x^4}.
\end{eqnarray*}
Note that the denominator is palindromic:
the sequence of coefficients $1,-1,-5,-1,1$
reads the same backwards as forwards.
This means that some of you may have gotten the correct answer
by an incorrect method
(by misapplying the relationship between
recurrence relations on the one hand
and denominator polynomials on the other).
\item[(b)]
{\it Use transfer matrices to find the generating function for the number of
irreducible domino-tilings of the 4-by-$n$ grid-graph. (Here an irreducible
tiling is one that cannot be decomposed into tilings of two smaller rectangles
of height 4.)}
Now we look at words of length $n+1$ that have the symbol N at the beginning
and at the end but nowhere in between. Let us leave aside the words NN and NAN
for the time being. Then a sequence of length $n+1$ that begins and ends with
N but has N nowhere in between cannot have an A in the middle anywhere, since
that A would have to be immediately preceded and immediately succeeded by an
$N$, contradicting irreducibility. Therefore, if we truncate the first and
last symbols, we are looking at words of length $n-1$ that don't contain N or
A. We can count them by taking the $(n-2)$nd power of the modified transfer
matrix
\[
N =
\left(
\begin{array}{cccc}
{\bf 0}&0&{\bf 1}&{\bf 0}\\
0&0&0&1\\
{\bf 1}&0&{\bf 0}&{\bf 0}\\
{\bf 0}&1&{\bf 0}&{\bf 0}
\end{array}
\right)
\]
obtained by removing the first and last row and column of $M$,
with rows and columns listed in the order T,M,B,O.
The boldface entries are the ones we want to sum
(note that neither the first nor last symbol of the new shortened word can be M
since we are supposed to be able to stick an N at the beginning and the end).
Since $N^2=I$,
it is easy to check that (for $n \geq 2$) the sum of the boldface entries
of $N^{n-2}$
(that is, the entries that are in neither the second row nor the second column)
is 3 when $n$ is even and 2 when $n$ is odd.
This still leaves the exceptional words NN and NAN
($n=2$ and $n=1$, respectively),
each of which corresponds to a unique irreducible tiling.
So the generating function is
$(x+x^2)+(3x^2+2x^3+3^x4+2x^5+\dots = x+4x^2+2x^3+3x^4+2x^5+\dots$,
or $B(x) = (x+4x^2+x^3-x^4)/(1-x^2)$.
(Note that in this case, as in the cases of rectangles of height 2, 3, or 4,
the number of irreducible tilings does not grow with the width of the
rectangle. However, this is atypical. Indeed, for all $k>4$, the number of
irreducible tilings of height $k$ and width $n$ does not stay bounded as $n$
gets large.)
It's worth noting that the degree of the numerator of $B(x)$
exceeds the degree of the denominator by 2.
This corresponds to the fact that
the recurrence relation $b_{n+2} - b_{n} = 0$
given to us by the denominator $1-x^2$
fails to kick in until $n>2$.
\item[(c)]
{\it Check your work by deriving your answer to (a) from your answer to (b)
and vice versa.}
A tiling of the sort counted by $A(x)$ is equivalent to
a sequence (possibly empty) of tilings of the sort counted by $B(x)$
(the irreducible components of the first tiling)
and has $x$-weight equal to the product of the weights of the components,
our general principle about repetition gives us
$A(x) = 1/(1-B(x))$.
Going in one direction, this gives us
\begin{eqnarray*}
A(x)
& = & (1-x^2)/((1-x^2)-(x+4x^2+x^3-x^4)) \\
& = & (1-x^2)/(1-x-5x^2-x^3+x^4)
\end{eqnarray*}
and in the other,
\begin{eqnarray*}
B(x) = 1 - (1-x-5x^2-x^3+x^4)/(1-x^2)
& = & ((1-x^2) - (1-x-5x^2-x^3+x^4))/(1-x^2) \\
& = & (x+4x^2+x^3-x^4))/(1-x^2).
\end{eqnarray*}
\end{itemize}
\item
\begin{itemize}
\item[(a)]
{\it Find a generating function for the number of spanning trees
of a 2-by-$n$ grid-graph.}
Let $t_n$ be the number of spanning Trees of the 2-by-$n$ grid
(so that $t_1=1$ and $t_2=4$)
and let $u_n$ be the number of Unconnected subgraphs of the 2-by-$n$ grid
which aren't spanning trees but which would become spanning trees
if the rightmost vertical edge was added in
(so that $u_1=1$ and $u_2=3$).
We will find a joint recurrence for the numbers $t_n$ and $u_n$.
Let's give labels to the three rightmost edges
of the 2-by-$n$ grid-graph:
$a$ is the upper rightmost edge,
$b$ is the lower rightmost edge,
and $c$ is the rightmost vertical edge.
A spanning tree of the 2-by-$n$ grid
(let's call it a $T$-graph of order $n$ for short)
is one of the following:
\begin{itemize}
\item
a $T$-graph of order $n-1$ with the edges $a$ and $b$ added;
\item
a $T$-graph of order $n-1$ with the edges $a$ and $c$ added;
\item
a $T$-graph of order $n-1$ with the edges $b$ and $c$ added; or
\item
a $U$-graph of order $n-1$ with the edges $a$, $b$ and $c$ added.
\end{itemize}
Hence $t_n = 3t_{n-1} + u_{n-1}$.
Likewise, a $U$-graph of order $n$
is one of the following:
\begin{itemize}
\item
a $T$-graph of order $n-1$ with the edge $a$ added;
\item
a $T$-graph of order $n-1$ with the edge $b$ added; or
\item
a $U$-graph of order $n-1$ with the edges $a$ and $b$ added.
\end{itemize}
Hence $u_n = 2t_{n-1} + u_{n-1}$.
I will demonstrate two ways of continuing the solution from this point.
Method I:
Define generating functions $T(x) = \sum_{n \geq 1} t_n x^n$
and $U(x) = \sum_{n \geq 1} u_n x^n$.
Multiplying the relation $t_{n+1} = 3t_n + u_n$ by $x^{n+1}$
and summing over $n \geq 1$
gives $T(x)-x = 3xT(x) + xU(x)$.
Likewise, multiplying the relation $u_{n+1} = 2t_n + u_n$ by $x^{n+1}$
and summing over $n \geq 0$
gives $U(x)-x = 2xT(x) + xU(x)$.
The former gives us
$(1-3x)T(x) - xU(x) = x$
and the latter gives us
$2xT(x) - (1-x)U(x) = -x$.
Solving, we get
$$T(x) = x/(1-4x+x^2) = x+4x^2+15x^3+56x^4+\dots$$
and
$$U(x) = (x-x^2)/(1-4x+x^2) = x+3x^2+11x^3+41x^4+\dots.$$
Method II:
Our joint recurrence gives us
$$
\left( \begin{array}{c} t_n \\ u_n \end{array} \right) =
\left( \begin{array}{cc} 3 & 1 \\ 2 & 1 \end{array} \right)
\left( \begin{array}{c} t_{n-1} \\ u_{n-1} \end{array} \right) .
$$
Hence both sequences will satisfy the linear recurrence relation
associated with the characteristic polynomial of the matrix
$\left( \begin{array}{cc} 3 & 1 \\ 2 & 1 \end{array} \right)$,
namely, $(\lambda-3)(\lambda-1)-(1)(2) = \lambda^2-4\lambda+1$.
(Here I am using $\lambda$ instead of $t$ as the variable
in the characteristic polynomial, so you won't confuse it with $t_n$.)
That is, we must have $t_{n+2}-4t_{n+1}+t_n=0$ for all $n \geq 1$.
Indeed, we can make this equation hold for all $n \geq 0$
if we adopt the convention $t_0 = 0$,
since we already know that $t_1 = 1$ and $t_2 = 4$.
Therefore, $T(x)$ must be of the form $p(x)/(1-4x+x^2)$
where $p(x)$ is a polynomial of degree less than 2.
To find $p(x)$, it suffices to know three consecutive values of $t_n$.
But we already know $t_0$, $t_1$, and $t_2$.
Multiplying $T(x) = 0 + x + 4x^2 + \dots$ by $1-x+4x^2$
gives $0+x+0x^2+\dots$,
so $p(x) = x$.
and $T(x) = x/(1-4x+x^2)$.
\item[(b)]
{\it These numbers turned up in a homework problem you did
earlier in the course. Which one was it?}
These are the same numbers that turned up in problem 1 of assignment 5,
as the coefficients of the generating function $B(x)$;
there, the coefficients counted domino tilings of 3-by-$(2n+1)$ rectangles
from which a corner has been removed.
However, our generating function $x/(1-4x+x^2)$
includes an extra factor of $x$
in the numerator.
So we have shown that the number of spanning trees of a 2-by-$n$ grid
equals the number of domino tilings of a 3-by-$(2n-1)$ rectangles
from which a corner has been removed.
\item[(c)]
{\it Is this a coincidence, or is there a connection between
the two problems?
That is, can you find a bijection between the two sorts
of combinatorial objects?}
We need to find a bijection between spanning trees of
the 2-by-$n$ grid graph
and perfect matchings of the $3-by-(2n-1)$ grid
from which a corner has been removed.
Enlarge the former by a factor of two
and superimpose the two pictures,
so that the four corner-vertices of the 2-by-$n$ grid
coincide with the corner-vertices (three present, one missing)
of the 3-by-$(2n-1)$ grid.
Let $v$ be the vertex of the 2-by-$n$ grid
that corresponds to the missing vertex of the 3-by-$(2n-1)$ grid.
Let $T$ be some spanning tree in the 2-by-$n$ grid.
Then, for every vertex $w \neq v$ of the 2-by-$n$ grid,
there is a unique path $w \rightarrow w' \rightarrow \dots \rightarrow v$
from $w$ to $v$ in $T$.
Let $a$ be the vertex of the 3-by-$(2n-1)$ grid
that coincides with $w$,
and let $b$ be the vertex of the 3-by-$(2n-1)$ grid
that coincides with the midpoint of the edge joining $w$ and $w'$.
In this way, each $w$ determines a pair $a,b$.
(You'll want to draw some picture of this, if you
haven't started drawing them already.)
It turns out that for any given $T$,
the pairs $a,b$ that arise in this way
are all disjoint from one another,
and that the set of associated edges
of the 3-by-$(2n-1)$ grid can be extended in exactly one way
to a perfect matching $M$ of the 3-by-$(2n-1)$ grid.
Moreover, each perfect matching $M$ arises in this way
from a unique spanning tree $T$.
\end{itemize}
\end{enumerate}
\end{document}