\documentclass[12pt]{article}
\newcommand{\sign}{{\rm sign}}
\pagestyle{empty}
\begin{document}
\begin{center}
Math 491, Problem Set \#19 \\
(due 12/9/03)
\end{center}
\medskip
\begin{enumerate}
\item
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)]
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.
\item[(b)]
Prove your conjectures from part (a) by induction on $n$.
\end{itemize}
\item
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)]
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.
\item[(b)]
Prove your conjectures from part (a) by induction on $n$.
\end{itemize}
\end{enumerate}
\end{document}