\documentstyle[12pt]{article}
\pagestyle{empty}
\begin{document}
\begin{center}
Math 491, Problem Set \#14 \\
(due 11/13/03)
\end{center}
\medskip
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{document}