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*}
Notes
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.