\documentstyle[12pt]{article}
\pagestyle{empty}
\begin{document}
\begin{center}
Math 491, Problem Set \#12 \\
(due 11/04/03)
\end{center}
\medskip
\begin{enumerate}
\item
Define the diagonal of a two-variable generating function
$$F(x,y) = \sum_{m,n} a_{m,n} x^m y^n$$
as the generating function
$$D(t) = \sum_n a_{n,n} t^n.$$
It is a theorem (which we will not have time to prove)
that the diagonal of any two-variable rational generating function
is an algebraic generating function.
Verify this claim in the particular case
$F(x,y) = 1/(1-x-y) = \sum_{m,n} \frac{(m+n)!}{m!n!} x^m y^n$
by expressing the diagonal $D(t)$ as an algebraic function.
Give as good a justification of your formula as you can.
\item
Call a sequence of $+1$'s $0$'s, and $-1$'s \emph{favorable}
if every partial sum is non-negative
and the total sum is 0.
Let $f(n)$ be the number of favorable sequences of length $n$.
Express the generating function $\sum_n f(n) x^n$
as an algebraic function of $x$.
\end{enumerate}
\end{document}