\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 $n<k$ the sum is clearly 0,
the above assertion can be rewritten as
$$\sum_{m:\:k \leq m \leq n} s(n,m) S(m,k) = 1_{\{n=k\}},$$
which is just the assertion that
the $s$-matrix and $S$-matrix are inverses of one another.)

Define a ``gizmo'' of type $(n,m,k)$
as a permutation of $[n]$ with $m$ cycles,
along with a partition of those $m$ cycles into $k$ blocks,
and assign it weight $(-1)^{n-m}$.
Since the number of permutations of $[n]$ with $m$ cycles is 
$(-1)^{n-m} s(n,m)$
and the number of partitions of $m$ things into $k$ blocks
is $S(m,k)$,
the sum $\sum_{m:\:k \leq m \leq n} s(n,m) S(m,k)$
is the sum of the weights of all gizmos of type $(n,m,k)$,
with $m$ varying between $k$ and $n$ (inclusive).

Say a block in some gizmo $\gamma$ is ample if it involves
more than one element of $[n]$;
that is, it either contains more than one cycle
or it involves a cycle of size greater than 1 (or both).
Since $n>k$, 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'<m_n$.

We have $P(0,n)=1$ and $P(1,n)=(1-q^{n+1})/(1-q)$ for all $n \geq 0$,
so $P(1,n)/P(0,n) = (1-q^{1+n})/(1-q^1)$ for all $n \geq 0$
and $P(m,0)/P(m-1,0) = (1-q^{m+0})/(1-q^m)$ for all $m \geq 1$,
as claimed.
It is also easy to check that $P(m,0)=1$
and $P(m,1)=(1-q^{m+1})/(1-q)$ for all $m \geq 0$,
so $P(0,n)/P(0,n-1) = (1-q^{0+n})/(1-q^m)$ for all $n \geq 1$
and $P(m,1)/P(m,0) = (1-q^{m+1})/(1-q^1)$ for all $m \geq 0$,
as claimed.

Next we use the induction hypothesis to prove
$P(m,n)/P(m-1,n) = (1-q^{m+n})/(1-q^{m})$.
Rewrite this as
$P(m,n) = P(m-1,n) (1-q^{m+n})/(1-q^{m})$.
We know (from (b)) that $P(m,n) = P(m-1,n) + q^m P(m,n-1)$,
so the thing we're trying to prove can be rewritten as
$P(m-1,n) (1-q^{m+n})/(1-q^{m}) = P(m-1,n) + q^m P(m,n-1)$
or
$$P(m-1,n) (1-q^{n})/(1-q^{m}) = P(m,n-1).$$
But by the induction hypothesis we have
$P(m-1,n) = P(m-1,n-1) (1-q^{m-1+n})/(1-q^{n})$
and
$P(m,n-1) = P(m-1,n-1) (1-q^{m+n-1})/(1-q^{m})$;
dividing the first of these by the second
gives us what we need to prove.

Lastly we use the induction hypothesis to prove
$P(m,n)/P(m,n-1) = (1-q^{m+n})/(1-q^{n})$.
Rewrite this as
$P(m,n) = P(m,n-1) (1-q^{m+n})/(1-q^{n})$.
We know (from (b)) that $P(m,n) = P(m-1,n) + q^m P(m,n-1)$,
so the thing we're trying to prove can be rewritten as
$P(m,n-1) (1-q^{m+n})/(1-q^{n}) = P(m-1,n) + q^m P(m,n-1)$
or
$$P(m,n-1) (1-q^m)/(1-q^n) = P(m-1,n),$$
which we proved in the preceding paragraph.

This completes the proof.

Note that we can conclude as a corollary that
$P(m,n)=P(n,m)$ for all $m,n$
(though as we'll see there are easier ways to prove this!).

\end{itemize}
\end{enumerate}
\end{document}
