\documentstyle[12pt]{article}
\pagestyle{empty}
\begin{document}
\begin{center}
Math 192r, Problem Set \#10 \\
(due 10/23/01)
\end{center}
\medskip
\begin{enumerate}
\item
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.
\item
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)] Give a formula for $P(1,n)$ and for the generating function
$$\sum_{n \geq 0} P(1,n) x^n.$$

\item[(b)] 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.

\item[(c)] 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)$.

\item[(d)] Write a computer program to compute
the polynomial $P(m,n)$ for any input values $m,n$.

\item[(e)] 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$.

\item[(f)] Use the recurrence relation from (b)
to verify your conjectures from (e).

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