\documentclass[12pt]{article}
\newcommand{\sign}{{\rm sign}}
\pagestyle{empty}
\begin{document}
\begin{center}
Math 192r, Problem Set \#17 \\
(due 11/29/01)
\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}

\item
Consider a triangular array 
in which the top row is of length $n$,
the next row is of length $n-1$,
etc., with each row (other than the last)
being centered above the row beneath.
Whenever such an array contains four entries arranged like

\medskip
\begin{center}
(more)
\end{center}

\pagebreak

$$\begin{array}{ccc}
  & w &    \\
x &   &  y \\
  & z &
\end{array}$$
we'll say that these entries satisfy the diamond condition if
$wz-xy=1$.
If the diamond condition is satisfied everywhere,
we'll say that the array is a diamond pattern.
Thus, for instance, the array
$$\begin{array}{ccccccc}
a &   & b &   & c &   & d \\
  & e &   & f &   & g &   \\
  &   & h &   & i &   &   \\
  &   &   & j &   &   &
\end{array}$$
with $a,b,c,d,e,f,g$ non-zero
is a diamond pattern iff $h=(ef+1)/b$, $i=(fg+1)/c$,
and $j = (hi+1)/f$.

Note that if the top two rows of a diamond pattern contain no zeroes,
there is a unique way to extend down.
This is also true if the top two rows 
consist of distinct formal indeterminates.
Let $D(x_1,x_3,\dots,x_{2n+1};$
%kludge
$y_2,y_4,\dots,y_{2n})$ be
the bottom entry of a diamond pattern
whose first row is $x_1,x_3,\dots,x_{2n+1}$
and whose second row is $y_2,y_4,\dots,y_{2n}$.
By examining small cases, you will find that
$D(x_1,x_3,\dots,x_{2n+1};y_2,y_4,\dots,y_{2n})$ can always be expressed
as a multivariate Laurent polynomial.
Give a conjectural bijection between
the terms of this Laurent polynomial
and domino tilings of the 2-by-$(2n-2)$ rectangle (for $n \geq 1$).
Include also a conjecture governing the coefficients.

\item
Repeat the problem, but with the diamond condition $ad-bc=1$
replaced by the ``frieze condition'' $ad-bc=-1$.
Let $F(x_1,x_3,\dots,x_{2n+1};$
%kludge
$y_2,y_4,\dots,y_{2n})$ be
the bottom entry of a frieze pattern
whose first row is $x_1,x_3,\dots,x_{2n+1}$
and whose second row is $y_2,y_4,\dots,y_{2n}$.
By examining small cases, you will find that
$F(x_1,x_3,\dots,x_{2n+1};y_2,y_4,\dots,y_{2n})$ can always be expressed
as a multivariate Laurent polynomial.
Give a conjectural bijection between
the terms of this Laurent polynomial
and domino tilings of the 2-by-$(2n-2)$ rectangle (for $n \geq 1$).
Include also a conjecture governing the coefficients.

\end{enumerate}

\end{document}
