Exponential Generating Functions

Exponential Generating Functions

Recall from the Generating Functions page that if $(a_i)_{i=0}^{\infty}$ is a sequence of real numbers then the generating function $F$ of $(a_i)_{i=0}^{\infty}$ is defined to be:

(1)
\begin{align} \quad F(x) = a_0 + a_1x + a_2x^2 + ... + a_ix^i + ... \end{align}

We will now look at another type of generating function known as an exponential generating function which we define below.

 Definition: If $(a_i)_{i=0}^{\infty} = \{a_0, a_1, a_2, ... \}$ is a sequence of real numbers then the Exponential Generating Function of $(a_i)_{i=0}^{\infty}$ is $E(x) = \sum_{i=0}^{\infty} a_i \frac{x^i}{i!} = a_0 + a_1x + a_2 \frac{x^2}{2!} + ... + a_i \frac{x^i}{i!} + ...$.

For example, if $(a_i)_{i=0}^{\infty} = (1, 1, 1, ...)$ then the exponential generating function of $(a_i)_{i=0}^{\infty}$ is:

(2)
\begin{align} \quad E(x) = \sum_{i=0}^{\infty} 1 \cdot \frac{x^i}{i!} = \sum_{i=0}^{\infty} \frac{x^i}{i!} \end{align}

The series on the righthand side is simply the Maclaurin series for $e^x$ and so the generating function $E$ of $(a_i)_{i=0}^{\infty}$ is:

(3)
\begin{align} \quad E(x) = e^x \end{align}

For another example, let $t \in \mathbb{R}$ and let's try to find the exponential generating function of $(a_i)_{i=0}^{\infty} = (1, t, t^2, ...)$. We have that:

(4)
\begin{align} \quad E(x) = 1 + tx + t^2 \frac{x^2}{2!} + ... + t^i \frac{x^i}{i!} + ... \quad E(x) = \sum_{i=0}^{\infty} t^i\frac{x^i}{i!} \\ \quad E(x) = \sum_{i=0}^{\infty} \frac{(tx)^i}{i!} \end{align}

Since $\sum_{i=0}^{\infty} \frac{x^i}{i!} = e^x$ we must have that the exponential generating function $E$ of $(a_i)_{i=0}^{\infty}$ is:

(5)
\begin{align} \quad E(x) = e^{tx} \end{align}

So what's so advantageous of using exponential generating functions? The first is that the regular generating functions we've already looked at are more useful when the terms of $(a_i)_{i=0}^{\infty}$ arise from the counting of combinations. The exponential generating functions are useful when the terms of $(a_i)_{i=0}^{\infty}$ arise from the counting of permutations.