Exponential Generating Functions

Notes

Trotter Chapter 8

Also see: Generating Functions#Trotter Chapter 8: Generating Functions

In the case of marbles in a can, or boxes to pack in a truck, is independent of order. What do we do if we have a problem in which order matters?

In these situations we want to use exponential generating functions. We define an analogous function to $ \dfrac{1}{1-x} $ to generate the sequence 1,1,1,1,...: we use the series expansion

$ e^x = \sum_{n \geq 0} \dfrac{x^n}{n!} $

which gives a basic exponential generating function of:

$ E(x) = \sum_{n \geq 0} \dfrac{x^n}{n!} $

As before, we will seek to put all functions/sequences of interest in terms of this base function.

EXAMPLE Counting Ternary Strings

Suppose we have ternary strings (numbers consisting of the digits 0, 1, and 2) of length n, and we wish to know how many of these strings have an even number of 0s.

To solve this problem, we apply a formulaic procedure:

First, we determine the generating function for each of the possible choices (0, 1, 2 in this case).

Then, we multiply the generating functions together to get the overall generating function.

For 1s and 2s, we have as many digits as we would like, so the generating functions are the normal 1, 1, 1, 1 series:

$ \begin{align} E_1(x) &=& e^x \\ E_1(x) &=& \sum_{n \geq 0} \dfrac{x^n}{n!} \end{align} $

$ \begin{align} E_2(x) &=& e^x \\ E_2(x) &=& \sum_{n \geq 0} \dfrac{x^n}{n!} \end{align} $

For the 0s, we can only have an even number of terms, so we need the series

$ 1 + \dfrac{x^2}{2!} + \dfrac{x^4}{4!} + \dots $

Unlike with linear generating functions, where complex numbers eliminate particular terms, exponential functions make this a little easier to do.

Start by writing out the exponential sequence that we are using:

$ e^{x} = 1 + \dfrac{x}{1!} + \dfrac{x^2}{2!} + \dfrac{x^3}{3!} + \dfrac{x^4}{4!} + \dots $

then substitute -x for x, to get a slightly different series:

$ e^{-x} = 1 - \dfrac{x}{1!} + \dfrac{x^2}{2!} - \dfrac{x^3}{3!} + \dfrac{x^4}{4!} - \dots $

If we add these two series together, the odd terms will cancel out, and we will have precisely the terms we want. This identity can be written:

$ \dfrac{e^x + e^{-x}}{2} = 1 + \dfrac{x^2}{2!} + \dfrac{x^4}{4!} + \dots $

Now we have the generating function for the 0 digit:

$ E_0(x) = \dfrac{e^x + e^{-x}}{2} = \sum_{k \geq 0} \dfrac{x^{2k}}{(2k)!} $

Now the overall generating function becomes:

$ \begin{align} E(x) &=& E_0(x) E_1(x) E_2(x) \\ &=& (e^x) (e^x) \left( \dfrac{e^x+e^{-x}}{2} \right) \\ &=& \dfrac{e^{3x} + e^x}{2} \end{align} $

Now the exponential functions can be converted to infinite series, and the series can be combined and simplified to yield the series form of the generating function.

$ \begin{align} \dfrac{e^{3x}+e^x}{2} &=& \dfrac{1}{2} \left( \sum_{n \geq 0} \dfrac{(3x)^n}{n!} + \sum_{k \geq 0} \dfrac{(x)^n}{n!} \right) \\ &=& \dfrac{1}{2} \left( \sum_{k \geq 0} \dfrac{ 3^n x^n + x^n}{n!} \right) \\ &=& \dfrac{1}{2} \left( \sum_{k \geq 0} (3^n + 1) \dfrac{x^n}{n!} \right) \end{align} $

What this means, in the end, is that the coefficient of the nth term of the infinite series expansion of our generating function is

$ \dfrac{3^n+1}{n!} $

and we can obtain a closed-form expression for the total number of ternary strings of length n having an even number of 0s. It is:

$ 3^n + 1 $