Counting With Generating Functions

Generating functions can be used for counting.

Consider the problem of finding the number of trees with internal nodes.

Let $T$ be the set of all binary trees. Let $|t|$ be the number of internal nodes in tree $t$ . Let $T_{N}$ be the number of trees with $|t|=N$ .

Then $T(z)=\sum_{t\in T}z^{|t|}=\sum_{N\ge0}T_{N}z^{N}$ .

Note the two different ways of writing the sum.

General Approach

Let $P$ be the set of all given objects.
Let $p\in P$ be an element of that object.
Let $P_{N}$ be the number of elements with $|p|=N$ .
Let $cost(p)$ be the “cost” of $p$ .
Let $P_{Nk}$ be the number of $p$ with $|p|=N$ and $cost(p)=k$ .
Define the cumulative cost to be $C_{N}=\sum_{k\ge0}kP_{Nk}$ .
Define the cumulative function to be $C(z)=\sum_{N\ge0}C_{N}z^{N}=\sum_{p\in P}cost(p)z^{|p|}$ .

Now the expected cost of size $N$ is:

$\begin{equation*} \frac{C_{N}}{P_{N}} \end{equation*}$

Or, using generating functions:

$\begin{equation*} \frac{\left[z^{N}\right]C(z)}{\left[z^{N}\right]P(z)} \end{equation*}$

Note that this equality:

$\begin{equation*} C(z)=\sum_{N\ge0}C_{N}z^{N}=\sum_{p\in P}cost(p)z^{|p|}. \end{equation*}$

allows you to generate identities by computing something in two different ways.