Counting With Generating Functions

Posted by Beetle B. on Mon 22 September 2014

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.