\documentclass[12pt]{article}
\newcommand{\sign}{{\rm sign}}
%\pagestyle{empty}
\begin{document}
\begin{center}
Math 192r, Problem Set \#17 --- 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{{\it if $j=i$}}, \\
	y_i     & \mbox{{\it if $j=i+1$}}, \\
	z_{i-1} & \mbox{{\it if $j=i-1$}}, \\
	0 & \mbox{{\it 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).

\item
{\it 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}
$$\begin{array}{ccc}
  & w &    \\
x &   &  y \\
  & z &
\end{array}$$
{\it 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}$$
{\it 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$.}

{\it 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.}

We readily compute:
$$D(x_1,x_3;y_2) = y_2$$
$$D(x_1,x_3,x_5;y_2,y_4) = y_2 x_3^{-1} y_4 + x_3^{-1}$$
$$D(x_1,\dots,y_6) = y_2 x_3^{-1} y_4 x_5^{-1} y_6 
+ y_2 x_3^{-1} x_5^{-1} + x_3^{-1} x_5^{-1} y_6 
+ x_3^{-1} y_4^{-1} x_5^{-1} + y_4^{-1}$$
In a 2-by-$(2n-2)$ rectangle,
number the $2n-1$ lattice-points on the horizontal mid-line 2 through $2n$.
Given any tiling $T$ of the rectangle,
let $a(i)$ ($2 \leq i \leq 2n$)
be the number of dominos in $T$ lying wholly within
the 2-by-2 square centered at the $i$th point on the mid-line,
so that $0 \leq a(i) \leq 2$,
and let $b(i) = 1 - a(i)$,
so that $-1 \leq b(i) \leq 1$.
Define the weight of $T$
to be
$$\left( \prod_{\mbox{$i$ odd}}  x_i^{b(i)} \right)
  \left( \prod_{\mbox{$i$ even}} y_i^{b(i)} \right).$$
Then one may conjecture (and as we'll see it is indeed the case) that
$D(x_1,x_3,\dots,x_{2n+1};y_2,y_4,\dots,y_{2n})$ is equal to
the sum of the weights of all the tilings $T$ of the 2-by-$(2n-2)$ rectangle.
Note that this would imply in particular that all coefficients are 1,
which is not obvious a priori.
In fact, it is not obvious that
the rational functions $D(\dots)$
can be expressed as Laurent polynomials.
And even if one knows that these functions are Laurent polynomials, 
it is not obvious a priori that the coefficients are positive.
(If you are tempted to think that a quotient of two polynomials with positive
coefficients must have positive coefficients,
consider that $(x^3+y^3)/(x+y) = x^2-xy+y^2$.)

\item
{\it 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.}

We readily compute:
$$F(x_1,x_3;y_2) = y_2$$
$$F(x_1,x_3,x_5;y_2,y_4) = y_2 x_3^{-1} y_4 - x_3^{-1}$$
$$F(x_1,\dots,y_6) = y_2 x_3^{-1} y_4 x_5^{-1} y_6 
- y_2 x_3^{-1} x_5^{-1} - x_3^{-1} x_5^{-1} y_6 
+ x_3^{-1} y_4^{-1} x_5^{-1} - y_4^{-1}$$
So one may conjecture that we have the same Laurent monomials as before,
only with non-trivial signs.
One may also conjecture that the sign is plus or minus
according to whether the number of vertical dominos
is twice an even number or twice an odd number.
We'll see that both conjectures are true.

\end{enumerate}

\end{document}
