\documentstyle{article}

\setlength{\topmargin}{-0.8in}
\setlength{\oddsidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.25in}
\pagestyle{empty}

\newtheorem{theorem}{Theorem}
\newtheorem{principle}{Principle}

\begin{document}

\noindent
{\large Design and Analysis of Algorithms \hfill Neal Young}

\noindent
{\large Computer Science 45 \hfill}

\vspace{.3in}

{\LARGE 
\begin{center}
{\large Notes on generating functions}
\end{center}}
\vspace{.2in}

My intention here is to just give you a brief introduction
to pique your interest and familiarize you with the ideas.
Check out the reference by Vitter and Flajolet \cite{Vitter90}
for further and more comprehensive info on generating functions.
Another reference for discrete math in general is the text
Concrete Math \cite{Graham:CM94}.
I expect you could find Mathematica or Maple packages to play with
on the net, one possible lead is
\cite{Devitt:1993:COT}.

\paragraph{Example --- the symbolic method.}
How many distinct $n$-node binary trees are there?
The {\em ordinary generating function} for the set of binary trees is
$$b(z) = \sum_{n=0}^{\infty} b_n z^n,$$
where $b_n$ is the number of binary trees of size $n$.
In the function $b$, there is one term $z^n$ of ``size'' $n$
for each tree of size $n$.
Postponing for a minute the question of what purpose this serves,
can we find a simpler form for the function $b$?
Here is a simple set of rules defining the binary trees:
\begin{enumerate}
\item The tree consisting of a single node is a binary tree.
\item If a tree $T$ is a binary tree,
  then the tree formed by creating a new root $r$
  and making $T$ the single subtree of $r$ is a binary tree.
\item If trees $T_1$ and $T_2$ are binary trees,
  then the tree formed by creating a new root $r$
  and making $T_1$ and $T_2$ the left and right subtrees of $r$
  is a binary tree.
\end{enumerate}
From this set of rules we can see the following equivalence:
$$ B \equiv \{\cdot\}
~\cup~ \left(\{\cdot\}\times B\right)
~\cup~ \left(\{\cdot\}\times B \times B\right).$$
Here ``$\cdot$'' represents a single node
and ``$\equiv$'' means there is a size-preserving bijection (a one-to-one and
onto function $f$ such that the size of $x$ equals the size of $f(x)$)
between the set on the left and the set on the right.
Replacing each root ``$\cdot$'' by a ``$z$'' (a term of ``size'' 1)
and replacing the set union by addition yields the corresponding equivalence:
$$b(z) = z + z\times b(z) + z\times b(z)\times b(z).$$
Solving for $b(z)$ using the quadratic formula yields
$$b(z) = \frac{1-z\pm\sqrt{1-2z-3z^2}}{2z}.$$
From this closed form and a little algebra,
we can see that $b(z)$ is well-defined as long as $z \le 1/3$
--- for larger values, the term inside the square root becomes negative.
Amazingly, from this it follows directly (for reasons discussed below)
that $b_n$ grows roughly like $3^n$.
With a little more work, an exact form for $b_n$ can be obtained.

\paragraph{Example --- recurrence relations.}
The Fibonacci numbers are defined by the following recurrence:
$$f_n = \cases{1 & $n=0$
  \cr f_{n-1} + f_{n-2} & $n > 0$
  \cr 0 & $n < 0$.}$$
The corresponding generating function is $f(z) = \sum_n^\infty f_n z^n.$
Can we find a simple form for $f(z)$?  Using the recurrence, we get
\begin{eqnarray*}
f(z) & = & \sum_n f_n z^n
\\ & = & f_0 + \sum_{n>0} (f_{n-1} + f_{n-2}) z^n
\\ & = & 1 + \sum_n f_{n-1}z^n + \sum_n f_{n-2}z^n
\\ & = & 1 + zf(z)+ z^2f(z).
\end{eqnarray*}
Solving for $f$ yields
$$f(z) = \frac{1}{1-z-z^2}.$$
From this we can see that $f$ is well-defined as long as
$z$ is less than $r=\frac{\sqrt{5}-1}{2}$ --- the smallest root of $1-z-z^2$.
From the general principle described below, it follows that $f_n$
grows roughly like $(1/r)^n \approx 1.62^n$.

\paragraph{Estimating the rate of growth from the smallest singularity.}
In the above examples, we used the following rule of thumb:
\begin{principle} (Singularity principle)
  Let $f(z)$ be any generating function with non-negative coefficients.

  If $f(a)$ is well-defined for some constant $a$,
  then $f_n$ is $o(a^{-n})$.

  If $f(b)$ is not well-defined for some constant $b$,
  then $f_n$ is not $O(1/c^n)$ for any constant $c>b$.
\end{principle}
We can summarize this by saying that the best exponential approximation
to the rate of growth of $f_n$ is $1/r^n$,
where $r$ is the smallest singularity of $f(z)$,
in other words,
$r$ is the largest value such that for all $z<r$, $f(z)$ is well-defined.

Why is this the case?
If $f(a)$ is well-defined, then the infinite sum $\sum_n f_n a^n$ converges.
Its terms must tend to zero as $n$ tends to infinity:
$$\lim_{n\rightarrow\infty} f_n a^n = 
\lim_{n\rightarrow\infty} \frac{f_n}{a^{-n}} = 0.$$
This establishes the first part of the principle:
$f_n = o\left(a^{-n}\right)$.

On the other hand, let $b$ and $c$ be as in the second part of the principle:
$f(b)$ is not well-defined and $b<c$.
Suppose for contradiction that $f_n$ is $O(c^{-n})$.
Then $f_n b^n = O((b/c)^n)$, so that
$$\sum_n f_n b^n = O\Big(\sum_n (b/c)^n\Big)
= O\left(\frac{1}{1-b/c}\right) = O(1).$$
This contradicts our assumption that $f(b)$ was not well-defined.

\paragraph{Symbolic derivations --- general principles.}
Here are a few general principles for {\em deriving} generating functions:
Suppose sets $A$ and $B$ have generating functions $a(z)$ and $b(z)$,
respectively.
\begin{itemize}
\item $A\cup B$ has generating function $a(z)+b(z)$,
  provided $A$ and $B$ are disjoint.
\item $A\times B$ (the Cartesian product) has generating function $a(z)b(z)$.
\item $A^k$ (the Cartesian product of $A$ with itself $k$ times)
  has generating function $a(z)^k$.
\item $A^* = \cup_{i\ge 0} A^i$
  has generating function $\frac{1}{1-a(z)}$.
  ($A^*$ is called the Kleene closure of $A$,
  its elements are the finite sequences of elements from $A$)
\end{itemize}
(The rule for Cartesian products assumes that the ``size'' of an element
$(\alpha,\beta)$ is the sum of the sizes of $\alpha$ and $\beta$.
This was the case in the binary tree example.
The subsequent rules have a similar assumption.)

Why are these principles true?
Take the Cartesian product rule for example.
For every element $\alpha \in A$ and $\beta \in B$,
there is a term $z^i$ in $a(z)$ and a term $z^j$ in $b(z)$,
where $i$ and $j$ are the sizes of $\alpha$ and $\beta$, respectively.
In the product $a(z)b(z)$,
the pair $(\alpha,\beta)$ thus contributes a single term $z^{i+j}$
of ``size'' equal to the size of the pair $(\alpha,\beta)$.
More formally, we can write
$$a(z)b(z) = \Big(\sum_i a_i z^i\Big)\Big(\sum_j b_j z^j\Big)
= \sum_{i,j} a_i b_j z^{i+j}
= \sum_n \Big(\sum_{i+j=n} a_i b_j\Big) z^n.$$
Since the number of pairs of size $n$ in $A\times B$
is $\sum_{i+j=n} a_i b_j$, this proves the principle.

\paragraph{A canonical example.}
How many $k$-digit decimal numbers are there whose digits sum to $n$?
Let $D$ be the set of digits $\{0,1,2,3,4,5,6,7,8,9\}$.
For this problem, we think of each digit as having a size equal to itself.
With this interpretation,
the generating function for $d(z)$
is $1+z+z^2+\cdots+z^9 = \frac{1-z^{10}}{1-z}$.

The set of $k$-digit numbers is then $D^k$.
The generating function for $D^k$ is 
$d(z)^k = \left(\frac{1-z^{10}}{1-z}\right)^k$.
Here the ``size'' we associate with a $k$-digit number
is just the sum of the sizes of the digits.

The singularity principle says that the $n$th coefficient grows like $1^n$ ---
this time it's not so useful!  On the other hand, note that for fixed $k$,
this generating function has only finitely many terms,
so we have to be a little more careful when asking questions
about the asymptotics.

\paragraph{Arbitrary-degree rooted trees.}
Let $t_n$ be the number of distinct rooted trees of size $n$.
We can define the set of rooted trees as follows:
\begin{enumerate}
\item A single node is a rooted tree.
\item If $T_1,T_2,\ldots,T_k$ is any finite sequence of rooted trees,
  then a new rooted tree can be formed by creating a new root node $r$
  and making the roots of the trees in the sequence
  the children of $r$.
\end{enumerate}
In fact, the first rule is the special case of the second
that occurs when $k=0$, so we can omit it.
This gives the equivalence for the set $T$ of rooted trees:
$$T \equiv \{\cdot\}\times T^*.$$
(Recall that $T^*$ represents finite sequences of elements of $T$.)
The generating function $t(z)$ thus satisfies
$$t(z) =  z \times \frac{1}{1-t(z)}.$$
Solving for $t(z)$ using the quadratic formula yields
$$t(z) =  \frac{1\pm\sqrt{1-4z}}{2}.$$
From the singularity principle,
it follows that $t_n$ grows roughly like $4^n$.

\paragraph{Exact answers.}
The singularity principle is useful for getting rough estimates
of the exponential rate of growth of the coefficients of a generating
function.  
Even more can be said about a generating function from its singularities,
however, the proper tool for this is complex analysis
and we don't pursue it further here.\footnote{%
  Some refinement is possible even without complex analysis.
  Here's a hint about pinning down the polynomial term.

  Suppose that $f(r)$ is well-defined but $f(z)$ is not well-defined for $z>r$.
  Compare the sum $\sum_n f_n/r^n$ (which converges)
  to the sum $\sum_n 1/n$ (which diverges).
  This will give you better upper bounds on $f_n$.
  Suppose further that $f'$ (the derivative of $f$)
  is {\em not} well-defined at $r$.
  Compare the sum $\sum_n nf_n/r^{n-1}$ (the derivative at $r$, which diverges)
  to $\sum_n 1/n^2$ (which converges).
  This will give you better lower bounds.

  If you are not so lucky that $f(r)$ is well-defined and $f'(r)$ isn't,
  then consider integrating or differentiating $f$ several times
  so that the resulting function has the property you want.
  Recall that each differentation introduces a linear term in each coefficient,
  whereas integration factors one out.
  }

Instead we give a few simple examples where exact expressions
can be obtained for the coefficients.

\paragraph{A few standard series.}
\begin{itemize}
\item $\frac{1}{1-z} = \sum_n z^n$.  This is the generating function
  for any set where there is exactly one item of each size.

\item $e^z = \sum_n z^n / n!$.  This function is an example of an {\em
    exponential} generating function, which we don't go into here.
  These kinds of generating functions are useful for counting ``labelled''
  structures --- for instance, binary trees where each node is assigned a
  number; another example is counting restricted classes of functions or
  permutations.

\item $(1+z)^m = \sum_n {m \choose n} z^n$.  This is the generating function
  for the binomial coefficients.  When $m$ is an integer, the $n$th coefficient
  represents the number of size-$n$ subsets of a set of size $m$.
\end{itemize}

\paragraph{Differentiation.}
Suppose you have a simple form $f(z)$
for the generating function $\sum_n f_n z^n$,
and you want a simple form for $\sum_n n f_n z^n$
--- that is, you want to introduce a linear term.
Note that $f'(z) = \sum_n n f_n z^{n-1}$,
so that the answer you want is just $zf'(z)$.
For instance, applying this to the generating function $1/(1-z) = \sum_n z^n$
gives $z/(1-z)^2 = \sum_n n z^n$.

You can also use differentation to get the exact form for the coefficients.
The general rule is
\begin{theorem}
  If $f(z) = \sum_n f_n z^n$, then
  $$f_n = \frac{f^{(k)}(0)}{n!}.$$
\end{theorem}
Here $f^{(k)}$ represents the $k$th derivative of $f$.
To prove it, first use induction to show that
$f^{(k)}(z) = \sum_n n(n-1)\cdots(n-k+1) f_n z^{n-k}$,
then substitute $k=n$ and $z=0$ (so all terms but the leading one drop out)
to get $f^{(k)}(0) = n! f_n$.

Repeated differentation can often be messy, but not always.
For example,
\begin{theorem}
  For any $m$, the coefficient of $z^n$ in $(1+z)^m$ is
  $${m \choose n} = \frac{m(m-1)\times(m-n+1)}{n!}.$$
\end{theorem}
This holds for arbitrary $m$, not just integer values.
To prove it, just note that differentiating $(1+z)^m$
$n$ times yields $m(m-1)\times(m-n+1)(1+z)^{m-n}$
and then apply the preceding theorem.

\paragraph{Substitution.}

From $\sum_n z^n = \frac{1}{1-z}$
it follows by substituting $2z$ for $z$
that $\sum_n 2^nz^n = \frac{1}{1-2z}$.
Similarly by substituting $z^2$ for $z$ one obtains
$\sum_n z^{2n} = \frac{1}{1-z^2}$.

\paragraph{Partial fractions.}
Recall that the generating function for the Fibonacci numbers is
$$f(z) = \frac{1}{1-z-z^2}.$$
Factor the denominator and separate into partial fractions:
\begin{eqnarray*}
  f(z) & = & \frac{1}{1-z-z^2}
  \\ & = & \frac{1}{(1-az)(1-bz)}
  \\ & = & \frac{a/(a-b)}{1-az} + \frac{b/(b-a)}{1-bz}
\end{eqnarray*}
Here $1/a$ and $1/b$ are the roots of $1-z-z^2$: $(1\pm\sqrt{5})/2$.
Letting $[z^n]f(z)$ denote the coefficient of $z^n$ in $f(z)$, we have
\begin{eqnarray*}
  [z^n] f(z) & = & \frac{a/(a-b)}{1-az} + \frac{b/(b-a)}{1-bz}
  \\ & = & \frac{a}{a-b}[z^n]\frac{1}{1-az} + \frac{b}{b-a}[z^n]\frac{1}{1-bz}
  \\ & = & \frac{a}{a-b}a^n + \frac{b}{b-a}b^n
  \\ & = & \frac{a^n - b^n}{a-b}.
\end{eqnarray*}

\nocite{Graham:CM94}
\nocite{Vitter90}
\nocite{Devitt:1993:COT}

\bibliographystyle{plain}
\bibliography{gen-fns.bib}
\end{document}

