\documentstyle[12pt]{article}
\begin{document}
\begin{center}
Math 192r, Problem Set \#10: Solutions \\
\end{center}
\medskip
\begin{enumerate}
\item
{\it Using a sign-reversing involution,
prove that for all $n>k$,
the sum $\sum_{m:\:k \leq m \leq n} s(n,m) S(m,k)$ equals zero.}
(Note: Since for $n=k$ the sum is clearly 1
and for $nk$, there is at least one ample block in $\gamma$.
Let $x$ be the smallest element of $[n]$
that lies in an ample block of $\gamma$,
and let $y$ be the second-smallest element in this block.
If $x$ and $y$ are in the same cycle,
say as $(x a b \dots d y e f \dots h)$,
replace that cycle by the pair of cycles
$(x a b \dots d)$ and $(y e f \dots h)$,
calling the resulting gizmo $\gamma'$.
Note that the block of $\gamma'$ that contains these two new cycles is ample,
that $x$ is the smallest element of $[n]$
that lies in an ample block of $\gamma'$,
and that $y$ is the second-smallest element in this block.
On the other hand, if $x$ and $y$ are in different cycles,
say as $(x a b \dots d)$ and $(y e f \dots h)$,
replace that pair of cycles by $(x a b \dots d y e f \dots h)$,
calling the resulting gizmo $\gamma'$.
Note that the block of $\gamma'$ that contains the merged cycle is ample,
that $x$ is the smallest element of $[n]$
that lies in an ample block of $\gamma'$,
and that $y$ is the second-smallest element in this block.
We see that $\Phi: \gamma \mapsto \gamma'$
is an involution.
Also, when $\gamma$ has $m$ cycles,
$\gamma'$ has $m \pm 1$ cycles,
so that $\Phi$ is sign-reversing.
Hence the sum of the weights of all the gizmos of type $(n,m,k)$
(with $n,k$ fixed and satisfying $n>k$
and with $m$ varying between $k$ and $n$ inclusive)
is zero.
\item
{\it Consider the subset of the square grid
bounded by the vertices $(0,0)$, $(m,0)$, $(0,n)$, and $(m,n)$,
and let $q$ be a formal indeterminate.
Let the weight of the horizontal grid-edge joining $(i,j)$ and $(i+1,j)$
be $q^{j}$ (for all $0 \leq i \leq m-1$ and $0 \leq j \leq n$),
and let each vertical grid-edge have weight 1.
Define the weight of a lattice path of length $m+n$ from $(0,0)$ to $(m,n)$
to be the product of the weights of all its constituent edges.
Let $P(m,n)$ be the sum of the weights of all the lattice paths
of length $m+n$ from $(0,0)$ to $(m,n)$, a polynomial in $q$.
(Note that putting $q=1$ turns $P(m,n)$
into the number of lattice paths of length $m+n$ from $(0,0)$ to $(m,n)$,
which is the binomial coefficient $\frac{(m+n)!}{m!n!}$.)}
\begin{itemize}
\item[(a)] {\it Give a formula for $P(1,n)$ and for the generating function
$$\sum_{n \geq 0} P(1,n) x^n.$$}
The $n+1$ paths from $(0,0)$ to $(1,n)$ have weight
$1$, $q$, $q^2$, \dots, $q^n$,
so $P(1,n) = 1+q+q^2+\dots+q^n = (1-q^{n+1})/(1-q)$
and
\begin{eqnarray*}
\sum_{n \geq 0} P(1,n) x^n
& = & \sum_{n \geq 0} \frac{x^n - q^{n+1} x^n}{1-q} \\
& = & \sum_{n \geq 0} \left( \frac{x^n}{1-q}-\frac{q(qx)^n}{1-q} \right) \\
& = & \frac{1}{(1-q)(1-x)}-\frac{q}{(1-q)(1-qx)} \\
& = & \frac{1}{(1-x)(1-qx)}
\end{eqnarray*}
\item[(b)] {\it Find (and justify) a recurrence relation relating
the polynomials $P(m,n)$, $P(m-1,n)$, and $P(m,n-1)$
that generalizes the Pascal triangle relation
for binomial coefficients.}
A path $p$ from $(0,0)$ to $(m,n)$
passes through either $(1,0)$ or $(0,1)$, but not both.
In the first case, let $p'$ be the path from $0$ to $(m-1,n)$
obtained from $p$ by snipping out the step from $(0,0)$ to $(1,0)$
and sliding the rest of the path one step to the left.
In this case the weight of $p'$ equals the weight of $p$.
In the second case, let $p'$ be the path from $0$ to $(m,n-1)$
obtained from $p$ by snipping out the step from $(0,0)$ to $(0,1)$
and sliding the rest of the path one step downward.
In this case the weight of $p'$ equals the weight of $p$
times $q^m$ (since each of the $m$ horizontal edges of $p$
has weight equal to $q$ times the weight of the
corresponding horizontal edge of $p'$).
Combining, we find that
$$P(m,n) = P(m-1,n) + q^m P(m,n-1).$$
Indeed, we can check this against (a),
using the trivial case $P(0,n)=1$:
the relation
$P(1,n) = P(0,n) + q^1 P(1,n-1)$
then amounts to
$1+q+q^2+\dots+q^n = 1 + q(1+q+\dots+q^{n-1})$,
which is true.
\item[(c)] {\it Let $F_m (x)$ denote $\sum_{n \geq 0} P(m,n) x^n$.
Use your answer from (b) to give a formula for $F_m (x)$
in terms of $F_{m-1} (x)$,
and from this derive a non-recursive formula for $F_{m} (x)$.}
Multiply the inset equation by $x^n$ and sum over all $n \geq 1$
(noting that the omitted term $P(m,0) x^0$ is just 1):
$$F_{m} (x) - 1 = (F_{m-1} (x) - 1) + q^m x F_{m} (x)$$
This gives
$(1 - x q^m) F_{m} (x) = F_{m-1} (x)$
so that
$$F_{m} (x) = F_{m-1} (x) / (1 - x q^m).$$
Indeed, using this relation
and the base case $F_{0}(x) = 1/(1-x)$
we get the general formula
$$F_{m} (x) = \frac{1}{(1-x)(1-xq)\cdots(1-xq^m)}.$$
\item[(d)] {\it Write a computer program to compute
the polynomial $P(m,n)$ for any input values $m,n$.}
\begin{verbatim}
readlib(coeftayl);
F := proc(m) local i; product(1/(1-q^i*x),i=0..m); end;
P := proc(m,n) simplify(coeftayl(F(m),x=0,n)); end;
r := proc(m,n)
simplify(P(m,n)*P(m-1,n-1)/P(m-1,n)/P(m,n-1)); end;
\end{verbatim}
Note that the function {\tt{coeftayl}} is a good thing to use
when you want just one coefficient from a Taylor expansion;
it saves time.
\item[(e)] {\it Compute $P(m,n) / P(m-1,n)$
for various values of $m \geq 1$ and $n \geq 0$
and conjecture a formula for it.
Do the same for the ratio
$P(m,n) / P(m,n-1)$ with $m \geq 0$ and $n \geq 1$.}
A bit of playing shows that the first ratio equals
$$(1+q+q^2+\dots+q^{m+n-1})/(1+q+q^2+\dots+q^{m-1})$$
or $(1-q^{m+n})/(1-q^{m})$,
while the second ratio equals
or $(1-q^{m+n})/(1-q^{n})$.
That is, we conjecture that
$$P(m,n)/P(m-1,n) = (1-q^{m+n})/(1-q^{m})$$
for $m \geq 1$ and $n \geq 0$ and
$$P(m,n)/P(m,n-1) = (1-q^{m+n})/(1-q^{n})$$
for $m \geq 0$ and $n \geq 1$.
\item[(f)] {\it Use the recurrence relation from (b)
to verify your conjectures from (e).}
We prove the two conjectures simultaneously
by joint induction on $m,n$.
That is, we verify the first formula
for its base cases (where $m=1$ or $n=0$)
and the second formula
for its base cases (where $m=0$ or $n=1$),
and we then verify that both formulas hold for $m,n$
if both formulas are both assumed to hold when $m,n$
are replaced by integers $m',n'$
satisfying $m'+n'