\documentstyle[12pt]{article}
\begin{document}
\begin{center}
Math 491, Problem Set \#12: Solutions \\
\end{center}
\medskip
\begin{enumerate}
\item
{\it 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.}
From our work on Catalan numbers, we know that $\frac{1-\sqrt{1-4t}}{2t}
= \sum_{n=0}^{\infty} \left({2n \choose n} / (n+1)\right) t^n$;
if we multiply by $t$ and differentiate,
we cancel the $n+1$ in the denominator, obtaining
$(1-4t)^{-1/2} = \sum_{n=0}^{\infty} {2n \choose n} t^n$.
\item
{\it 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$.}
Let $F(x)$ be the generating function for all favorable sequences,
and $P(x)$ be the generating function for just the primitive ones,
where a favorable sequence is called primitive
iff it cannot be written as a concatenation of two or more
non-empty favorable sequences.
We have $F(x) = 1 + P(x) F(x)$ on general principles.
Furthermore, $P(x) = x + x^2 F(x)$,
since a primitive favorable sequence is either a sequence of length 1
whose sole term is 0
or else a $+1$ followed by a favorable sequence followed by a $-1$.
Hence
$$F(x) = 1 + (x + x^2 F(x)) F(x),$$
which gives the quadratic equation
$x^2 F(x)^2 + (x-1) F(x) + 1 = 0$.
Solving, we get
$$F(x) = \frac{1-x-\sqrt{1-2x-3x^2}}{2x^2}.$$
\end{enumerate}
\end{document}