\documentclass[12pt]{article}
%\pagestyle{empty}
\begin{document}
\begin{center}
Math 491, Problem Set \#18: Solutions \\
\end{center}
\medskip
\begin{enumerate}
\item
{\it Use Lindstrom's lemma,
the interpretation of domino tilings as routings,
and a computer,
in order to count the domino tilings of an 8-by-8 square.
(You will receive no credit for merely giving the correct answer.)}
Checkerboard-color the squares in the grid, so that the
upper-left square is shaded. Mark the mid-point of every vertical
edge that has a black square to its left or a white square to its
right (or both). It's easy to check that every possible placement
of a domino yields either zero or two marked points on its boundary.
Hence, if one fixes a domino tiling and draws connections between
all pairs of marked points that share a domino, one gets four
non-intersecting left-to-right lattice paths joining the four leftmost
marked points to the four rightmost marked points. Conversely, given
four such lattice paths, one can construct a tiling by taking all those
dominoes that cover an edge of the lattice path, along with all dominoes
that are centered on those marked points that do not lie on any of the
lattice paths. Hence there is a bijection between domino-tilings of the
8-by-8 grid and families of non-intersecting lattice paths joining the
sources $s_1,s_2,s_3,s_4$ to the sinks $t_1,t_2,t_3,t_4$ in a trellis-like
directed graph, with directed edges corresponding to the vectors $(1,1)$,
$(1,-1)$, and $(2,0)$. It is easy to see that the only way to connect
the $s_i$'s and the $t_j$'s via non-intersecting paths in this directed
graph is to connect $s_i$ to $t_i$ for $1 \leq i \leq 4$. Hence Lindstrom's
Lemma applies, and the number of families of non-intersecting lattice paths
is equal to the determinant of the 4-by-4 matrix $M$ whose $i,j$th entry
equals the number of lattice paths from $s_i$ to $t_j$.
To determine the entries of $M$, we introduce new vertices in a shifted
lattice that fills the holes in the lattice of marked points. (That is
to say, we now associated a point with every vertical edge.) The points
$s_1,s_2,s_3,s_4$ are the 2nd, 4th, 6th, and 8th points on the left edge
(and similarly for $t_1,t_2,t_3,t_4$). Then the $i,j$th entry of $M$
is equal to the $2i,2j$th entry of $AA^TAA^TAA^TAA^T$, where
$$
A = \left( \begin{array}{cccccccc}
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 1
\end{array} \right) .
$$
Using Maple, one gets
%\pagebreak
\begin{verbatim}
[ 22 68 30 48 10 12 1 1 ]
[ ]
[ 68 236 116 216 60 84 13 14 ]
[ ]
[ 30 116 62 128 41 61 11 12 ]
[ ]
[ 48 216 128 320 129 230 60 70 ]
[ ]
[ 10 60 41 129 63 128 40 48 ]
[ ]
[ 12 84 61 230 128 306 116 146 ]
[ ]
[ 1 13 11 60 40 116 52 68 ]
[ ]
[ 1 14 12 70 48 146 68 90 ]
\end{verbatim}
Extracting the sub-matrix
\begin{verbatim}
[ 236 216 84 14 ]
[ ]
[ 216 320 230 70 ]
[ ]
[ 84 230 306 146 ]
[ ]
[ 14 70 146 90 ]
\end{verbatim}
and taking its determinant, one gets 12988816.
\item
{\it Using the bijection between tilings and routings discussed in class,
Lindstrom's lemma, and Dodgson condensation,
prove that for all $a,b \geq 0$ and for $c=3$,
the number of ways to tile an $a,b,c,a,b,c$
semiregular hexagon with unit rhombuses is equal to
$$\frac{H(a+b+c)H(a)H(b)H(c)}{H(a+b)H(a+c)H(b+c)}$$
where
$H(0)=H(1)=1$ and
$H(n)=1!2!3! \cdots (n-1)!$ for $n > 1$.}
I might as well prove the claim for all $c$
(though you didn't have to).
Let $T(a,b,c)$ denote the number of rhombus tilings
of the $a,b,c,a,b,c$ semiregular hexagon.
It is easy to check that for all $a,b \geq 0$,
$T(a,b,0) = 1 = \frac{H(a+b+0)H(a)H(b)H(0)}{H(a+b)H(a+0)H(b+0)}$
and
$T(a,b,1) = \frac{(a+b)!}{(a)!(b)!} =
\frac{H(a+b+1)/H(a+b)}{(H(a+1)/H(a))(H(b+1)/H(b)}$
%kludge
$=\frac{H(a+b+1)H(a)H(b)H(1)}{H(a+b)H(a+1)H(b+1)}$.
We will prove the claim for $c>1$ using induction on $c$.
(For the homework problem, you don't need induction;
you just reduce the case $c=3$ to the case $c=2$
already solved in an earlier homework.)
Rhombus-tilings of the $a,b,c,a,b,c$ semiregular hexagon
correspond to routings with $c$ sources and $c$ sinks
in a directed graph
in which the number of paths from the $i$th source to the $j$th sink
equals $a+b \choose b-i+j$.
Therefore by Lindstrom's lemma we have
$T(a,b,c) = \det M(a,b,c)$
where $M(a,b,c)$ denotes the $c$-by-$c$ matrix
whose $i,j$th entry is $a+b \choose b-i+j$.
In view of the this,
Dodgson condensation tells us that
\begin{eqnarray*}
T(a,b,c) T(a,b,c-2) &=& T(a,b,c-1)^2 \\
& & - T(a+1,b-1,c-1) T(a-1,b+1,c-1).
\end{eqnarray*}
For slight notational convenience,
I'll re-index this as
$$T(a,b,c+1) T(a,b,c-1) = T(a,b,c)^2 - T(a+1,b-1,c) T(a-1,b+1,c).$$
The problem now reduces to algebraically verifying
that $T(a,b,c+1)$ must be given by the $H(\ )$-formula
if $T(a,b,c-1)$, $T(a,b,c)$, $T(a+1,b-1,c)$ and $T(a-1,b+1,c)$ are.
Equivalently, we must verify that if all five of these $T(\ )$-values
are as given by the $H(\ )$-formula, then the expression
$$T(a,b,c+1) T(a,b,c-1) - T(a,b,c)^2 + T(a+1,b-1,c) T(a-1,b+1,c)$$
must vanish.
If we trust Maple, then we can prove this
by noting that the final command in the string of commands
\begin{verbatim}
H := proc(n) product(k!,k=1..n-1); end;
T := proc(a,b,c) H(a+b+c)*H(a)*H(b)*H(c)
/H(a+b)/H(a+c)/H(b+c); end;
U := T(a,b,c)*T(a-2,b,c)-T(a-1,b,c)^2
+T(a-1,b-1,c+1)*T(a-1,b+1,c-1);
simplify(expand(U));
\end{verbatim}
gives the output {\tt{0}}.
However, if you're more skeptical,
here's a sketch of how you can show by hand
that the expression
$T(a,b,c+1) T(a,b,c-1) - T(a,b,c)^2 + T(a+1,b-1,c) T(a-1,b+1,c)$
vanishes
when each $T(\ )$ is expanded using the $H(\ )$-formula.
Write each of the three terms as a fraction,
and in each of the terms
divide the numerator by
$H(a+b+c-1)H(a+b+c)H(a-1)H(a)H(b-1)H(b)H(c-1)H(c)$
and the denominator by
$H(a+b)^2 H(a+c-1)H(a+c) H(b+c-1)H(b+c)$,
obtaining another messy expression.
But we have made progress:
where before we had a sum each term of which was a ratio of products
each factor of which was a value of the $H$-function,
we now have a sum each term of which is a ratio of products
each factor of which is a value of the factorial function,
Moreover, there are now some factors common to all three terms;
removing them gives
\begin{eqnarray*}
& \frac{(a+b+c)!(a-1)!(b-1)!(c)!}{(a+c)!(b+c)!} & \\
& - \frac{(a+b+c-1)!(a-1)!(b-1)!(c-1)!}{(a+c-1)!(b+c-1)!} & \\
& + \frac{(a+b+c-1)!(a)!(b)!(c-1)!}{(a+c)!(b+c)!}. &
\end{eqnarray*}
Removing common factors again gives us
$$(a+b+c-1)(c-1) - (a+c-1)(b+c-1) + (a)(b),$$
which vanishes.
\end{enumerate}
\end{document}