\documentclass[12pt]{article}
\newcommand{\sign}{{\rm sign}}
%\pagestyle{empty}
\begin{document}
\begin{center}
Math 491, Problem Set \#19: Solutions \\
\end{center}
\medskip
\begin{enumerate}
\item
{\it Let $P(n)$ and $Q(n)$
denote the numerator and denominator obtained
when the continued fraction
$$x_1+(y_1/(x_2+(y_2/(x_3+(y_3/\cdots +(y_{n-2}/(x_{n-1}+(y_{n-1}/x_n)))
\cdots)))))$$
is expressed as an ordinary fraction.
Thus $P(n)$ and $Q(n)$ are polynomials in the variables
$x_1,...,x_n$ and $y_1,...,y_{n-1}$.}
\begin{itemize}
\item[(a)]
{\it By examining small cases,
give a conjectural bijection between
the terms of the polynomial $P(n)$
and domino tilings of the 2-by-$n$ rectangle,
and a similar bijection between
the terms of the polynomial $Q(n)$
and domino tilings of the 2-by-$(n-1)$ rectangle,
as well as a conjecture that gives all the coefficients.}
We readily compute:
$$\frac{P(1)}{Q(1)} = \frac{x_1}{1}$$
$$\frac{P(2)}{Q(2)} = \frac{x_1 x_2 + y_1}{x_2}$$
$$\frac{P(3)}{Q(3)} = \frac{x_1 x_2 x_3 + y_1 x_3 + x_1 y_2}{y_2 + x_2 x_3}$$
To describe $P(n)$ in general, take a 2-by-$n$ rectangle
with its columns indexed 1 through $n$.
A tiling of such a rectangle by dominos
consists of vertical dominos and 2-by-2 blocks of horizontal dominos;
assign weight $x_k$ to a vertical domino
occupying the $k$th column
and weight $y_k$ to a block of horizontal dominos
occupying the $k$th and $k+1$st columns,
and give each tiling a weight equal to the product
of the weights of its vertical dominos
and of its 2-by-2 blocks of horizontal dominos.
Then one may conjecture that $P(n)$ is the sum of the weights
of all the domino tilings of the 2-by-$n$ rectangle.
Likewise for $Q(n)$, except that the rectangle
is a 2-by-$(n-1)$ rectangle
with columns indexed from 2 through $n$.
\item[(b)]
{\it Prove your conjectures from part (a) by induction on $n$.}
\end{itemize}
The base case is trivial.
To prove the general case,
let $P^+(n-1)$ and $Q^+(n-1)$ denote $P(n-1)$ and $Q(n-1)$ with all subscripts
increased by 1.
Then we have
$P(n)/Q(n) = x_1+(y_1/(P^+(n-1)/(Q^+(n-1))))
= (x_1 P^+(n-1) + y_1 Q^+(n-1)) / P(n-1)$
so that $P(n) = x_1 P^+(n-1) + y_1 Q^+(n-1)$ and $Q(n) = P^+(n-1)$.
If we assume for purposes of induction that
$P^+(n-1)$ is the weight-enumerator for domino tilings
of a rectangle of height 2 with rows indexed by 2 through $n$
and that $Q^+(n-1)$ is the weight-enumerator for domino tilings
of a rectangle of height 2 with rows indexed by 3 through $n$,
it follows that $x_1 P^+(n-1) + y_1 Q^+(n-1) = P(n)$
is the weight-enumerator for domino tilings
of a rectangle of height 2 with rows indexed by 1 through $n$.
The induction is even easier for $Q(n)$,
since it just involves reindexing.
(To be really fastidious, we would want to include in our proof
a verification that the polynomials
$P(n) = x_1 P^+(n-1) + y_1 Q^+(n-1)$ and $Q(n) = P^+(n-1)$
have no common factor.
This can be shown easily by induction.
Specifically, the fact that $P(n-1)$ and $Q(n-1)$ have no common factor
implies that $P^+(n-1)$ and $Q^+(n-1)$ have no common factor,
which implies that $x_1 P^+(n-1) + y_1 Q^+(n-1)$ and $P^+(n-1)$
have no common factor.)
\item
{\it Let $R(n)$ denote the determinant of the $n$-by-$n$ matrix $M$
whose $i,j$th entry is equal to}
$$\left\{ \begin{array}{ll}
x_i & \mbox{if $j=i$}, \\
y_i & \mbox{if $j=i+1$}, \\
z_{i-1} & \mbox{if $j=i-1$}, \\
0 & \mbox{otherwise.}
\end{array} \right.$$
\begin{itemize}
\item[(a)]
{\it By examining small cases,
give a conjectural bijection between
the terms of the polynomial $R(n)$
and domino tilings of the 2-by-$n$ rectangle,
and a conjecture for the coefficients.}
We readily compute:
$$R(1) = x_1$$
$$R(2) = x_1 x_2 - y_1 z_1$$
$$R(3) = x_1 x_2 x_3 - y_1 z_1 x_3 - x_1 y_2 z_2$$
$$R(4) = x_1 x_2 x_3 x_4 - y_1 z_1 x_3 x_4 - x_1 y_2 z_2 x_4
- x_1 x_2 y_3 z_3 + y_1 z_1 y_3 z_3$$
Decree that a vertical domino occupying column $k$ has weight $x_k$,
a horizontal domino in the first row occupying rows $k$ and $k+1$
has weight $y_k$,
and a horizontal domino in the second row occupying rows $k$ and $k+1$
has weight $z_k$.
Let the weight of a tiling be the product of the weights of its tiles,
together with a factor of $(-1)^r$
where $r$ is the number of 2-by-2 blocks of horizontal dominos.
Then one may conjecture that $R(n)$ equals the sums of the weights
of all the domino-tilings of a 2-by-$n$ rectangle.
\item[(b)]
{\it Prove your conjectures from part (a) by induction on $n$.}
\end{itemize}
We have $R(n) = \sum_{\pi} \prod_i m_{i,\pi(i)}$
where the sum is over all permutations of $1,...,n$.
The only permutations $\pi$ that make a non-zero contribution to $\det(M)$
are those for which $m_{i,\pi(i)} \neq 0$ for all $i=1,...,n$.
In particular, we must have $\pi(n)=n$ or $n-1$.
If $\pi(n)=n-1$, then we must have $\pi(n-1)=n$
(since there must exist $i$ with $\pi(i)=n$,
and $i=n$ and $i=n-1$ were the only two possibilities from the start).
If we sum $\prod_i m_{i,\pi(i)}$ over all $\pi$ with $\pi(n)=n$,
we get $x_n$ times the determinant $R(n-1)$,
while if we sum $\prod_i m_{i,\pi(i)}$ over all $\pi$
with $\pi(n)=n-1$ and $\pi(n-1)=n$,
we get minus $y_{n-1} z_{n-1}$ times the determinant $R(n-2)$,
with the minus sign coming from the transposition that switches $n-1$ and $n$.
(More formally: in the first case we replace $\pi$ by a permutation $\pi'$
on the set $\{1,...,n-1\}$ by deleting the 1-cycle $(n)$,
and in the second case we replace $\pi$ by a permutation $\pi"$
on the set $\{1,...,n-2\}$ by deleting the 2-cycle $(n-1 \ n)$.
We need merely note that $\sign(\pi')=\sign(\pi)$
while $\sign(\pi")=-\sign(\pi)$.)
Hence we have
$R(n)=x_n R(n-1) - y_{n-1} z_{n-1} R(n-2)$.
But it is easy to see that the sum of the weights of domino tilings
satisfies the same recurrence relation,
so the claim is proved
(once we check the initial conditions, which is easy).
\end{enumerate}
\end{document}