9.3: Bell Numbers and Exponential Generating Functions

Sometimes a recurrence relation involves factorials, or binomial coefficients. When this happens, it becomes difficult if not impossible to use ordinary generating functions to find an explicit formula for the nth term of the sequence. In some cases, a different kind of generating function, the exponential generating function, may succeed where an ordinary generating function fails.

Definition: Exponential Generating Function

The exponential generating function for the sequence \(a_0, a_1, . . .,\) is

\[\sum_{i=0}^{\infty} \dfrac{a_ix^i}{i!} \]

Obviously, the difference between this and an ordinary generating function comes from the factorial expression in the denominator. Cancellation between this and expressions in the numerator can lead to nicer compact expressions

Example \(\PageIndex{1}\)

The exponential generating function for the sequence \(1, 1, 1, . . .\) is

\(\dfrac{1}{0!} + \dfrac{x}{1!} + \dfrac{x^2}{2!} + ... \)

This is the Taylor series expansion for \(e^x\). Thus, \(e^x\) is the exponential generating function for \(1, 1, 1, . . .\).

We will not be using exponential generating functions in this class; we are just introducing the topic. We will go through one example of a sequence for which exponential generating functions are useful: the Bell numbers

Definition: Bell Number

The Bell number \(B_n\) is the number of partitions of \(\{1, . . . , n\}\) into subset.

Let’s look at the first few Bell numbers

Example \(\PageIndex{2}\)

There is only one way to partition \(\{1\}\) into subsets: \(\{1\}\), so \(B_1 = 1\).

There are two ways to partition \(\{1, 2\}\) into subsets: \(\{1\}\), \(\{2\}\), or \(\{1, 2\}\), so \(B_2 = 2\).

There are five ways to partition \(\{1, 2, 3\}\) into subsets: \(\{1\}\), \(\{2\}\), \(\{3\}\), or \(\{1, 2\}\), \(\{3\}\), or \(\{1, 3\}\), \(\{2\}\), or \(\{2, 3\}\), \(\{1\}\), or \( \{1, 2, 3\}\), so \(B_3 = 5\).

Probably after seeing the above examples, you don’t want to calculate larger Bell numbers directly. However, we can derive a recursive relation for these numbers. For this relation to work properly, we will define \(B_0 = 1\).

Proposition \(\PageIndex{1}\)

For \(n ≥ 1\), the nth Bell number

\[B_n = \sum_{k=1}^{n} \binom{n-1}{k-1} B_{n-k} \]

Proof

We’ll use a combinatorial proof of this statement. We know that Bn is the number of partitions of \(\{1, . . . , n\}\) into subsets.

For the other side of the equation, let’s consider the subset that contains the element \(n\), and call the cardinality of this subset \(k\). Since \(n\) is in this subset, \(k ≥ 1\), and since this is a subset of \({1, . . . , n}\), we have \(k ≤ n\), so \(1 ≤ k ≤ n\). There are \(\binom{n−1}{k−1}\) ways to choose the remaining \(k −1\) elements of this subset; that is, for any \(1 ≤ k ≤ n\), there are \(\binom{n−1}{k−1} \) ways to choose the subset of \({1, . . . n}\) that contains the element \(n\). For each of these ways, there are \(n − k\) other elements that must be partitioned, and by the definition of the Bell numbers, there are \(B_{n−k}\) ways to partition them into subsets. (Our definition of \(B_0 = 1\) deals with the case \(k = n\), ensuring that the \(\binom{n−1}{n−1} = 1\) way of choosing \(n\) to be in a single set of all \(n\) elements is counted once and only once.)

Thus, using the product and sum rules, we see that

\(B_n = \sum_{k=1}^{n} \binom{n-1}{k-1} B_{n-k} \)

Let us try to find the exponential generating function for the Bell numbers. When dealing with exponential generating functions, notice that the derivative of \(\dfrac{x^n}{n!}\) is \(n\dfrac{x^n}{n!} = \dfrac{x^{n−1}}{(n − 1)!}\), so taking derivatives often results in a nice expression that helps us find a nice expression for the coefficients. You already know a particularly nice example of this: the derivative of \(e^x\) is \(e^x\), which tells us that all of the coefficients in that exponential generating function are equal.

Define

\(B(x) = \sum_{i=0}^{\infty} B_i \dfrac{x^i}{i!} = B_0 + B_1 \dfrac{x}{1!} + B_2 \dfrac{x^2}{2!} +...+ B_n \dfrac{x^n}{n!} \)

Notice that the derivative of this is

\( \begin{equation} \begin{split} \dfrac{d}{dx} B(x) &= B_1 + B_2 \dfrac{x}{1!} + B_3 \dfrac{x^2}{2!} +...+ B_n \dfrac{x^{n-1}}{(n-1)!} \\ &= \sum_{n=1}^{\infty} B_n \dfrac{x^{n-1}}{(n-1)!} \end{split} \end{equation} \)

Using our recursive relation from Proposition 9.3.1, we see that this is

\( \begin{equation} \begin{split} \dfrac{d}{dx} B(x) &= \sum_{n=1}^{\infty} \left[ \sum_{k=1}^{n} \binom{n-1}{k-1} B_{n-k} \right] \dfrac{x^{n-1}}{(n-1)!} \\ &= \sum_{n=1}^{\infty} \left[ \sum_{k=1}^{n} \dfrac{(n − 1)!}{(k − 1)!(n − k)!} B_{n-k} \dfrac{x^{n-1}}{(n-1)!} \right] \\ &= \sum_{n=1}^{\infty} \left[ \sum_{k=1}^{n} \dfrac{1}{(k − 1)!(n − k)!} B_{n-k} x^{n-1} \right] \\ &= \sum_{n=1}^{\infty} \left[ \sum_{k=1}^{n} \dfrac{x^{k-1}}{(k − 1)!} B_{n-k} \dfrac{x^{n-k}}{(n-k)!} \right] \\ \end{split} \end{equation} \)

Notice that for each value of \(n\), as \(k\) goes from \(1\) to \(n\) the values \(k − 1\) and \(n − k\) take on every pair of non-negative integral values that add up to \(n\). Thus, as \(n\) goes from \(1\) to infinity, the values \(k − 1\) and \(n − k\) take on every possible pair of non-negative integral values. Therefore, we can rewrite this expression as

\[ \begin{equation} \begin{split} \dfrac{d}{dx} B(x) &= \sum_{j=0}^{\infty} \left[ \sum_{i=0}^{\infty} \dfrac{x^j}{j!} B_i \dfrac{x^i}{i!} \right] \\ &= \sum_{j=0}^{\infty} \dfrac{x^j}{j!} \left[ \sum_{i=0}^{\infty} B_i \dfrac{x^i}{i!} \right] \\ &= \left[ \sum_{j=0}^{\infty} \dfrac{x^j}{j!} \right] \left[ \sum_{i=0}^{\infty} B_i \dfrac{x^i}{i!} \right] \end{split} \end{equation} \]

Now, consider the derivative of \(e^{−(e^x)}B(x)\). By the product and chain rules, this is

\(e^{−(e^x)}e^x B(x) - B(x)e^{−(e^x)}e^x = 0 \),

so it must be the case that \(e^{−(e^x)}B(x)\) is constant, say \(e^{−(e^x)}B(x) = c\). Then \(B(x) = ce^{(e^x)}\).

Since

\(B(0) = \sum_{n=0}^{\infty} B_n \dfrac{0^n}{n!} = 1 + \sum_{n=1}^{\infty} 0 = 1 \),

(recall that \(0^0 = 0\), or if you don’t like that, simply use the expansion of \(B(0)\)), we see that

\(ce^{e^0} = ce^1 = ce = 1\),

so \(c = e^{−1}\). Hence

\(B(x) = e^{−1} e^{(e^x)} = e^{(e^x−1)} \).

There are techniques to extract coefficients from expressions like this, also, but we will not cover these techniques in this class.

Exercise \(\PageIndex{1}\)

1. Find \(B_4\).
2. What is the exponential generating function for the sequence \(a_i = i!\) for every \(i ≥ 0\)? Give the sequence in both an expanded and a closed form.
3. What is the exponential generating function for the sequence \(b_i = \dfrac{(i + 1)!}{2}\) for every \(i ≥ 0\)? Give the sequence in both an expanded and a closed form.