Skip to main content

Section 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 \(n\)th 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.

In this section we will be using techniques from calculus. This section is not required for understanding other parts of this book, and the material can be omitted or skimmed over.

Definition 9.3.1.

The exponential generating function for the sequence \(a_0, a_1, \ldots\text{,}\) is

\begin{equation*} \sum_{i=0}^\infty \frac{a_ix^i}{i!}\text{.} \end{equation*}

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.

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

\begin{equation*} \frac{1}{0!}+\frac{x}{1!}+\frac{x^2}{2!}+\ldots\text{.} \end{equation*}

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

We will not be using exponential generating functions in this course; 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. As with many other topics in this course, although the Bell numbers are named for Eric Temple Bell (1883—1960), who wrote about them in the \(1930\)s, he does not deserve credit for their discovery. They go back to medieval Japan, and had been much studied by mathematicians prior to Bell's writing.

Definition 9.3.3.

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

In case you are not familiar with the term, a partition of a set \(X\) into subsets is a collection of subsets \(X_1, \ldots, X_k\) with the properties that:

  • \(\bigcup_{i=1}^k X_i=X\text{;}\) and
  • for any \(1 \le i,j \le k\) with \(i \neq j\text{,}\) we have \(X_i \cap X_j=\emptyset\text{.}\)

In other words, every element of \(X\) must appear in exactly one of the subsets.

Let's look at the first few Bell numbers.

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

There are two ways to partition \(\{1,2\}\) into subsets: take the two subsets \(\{1\}, \{2\}\text{,}\) or put everything into the single subset \(\{1,2\}\text{,}\) so \(B_2=2\text{.}\)

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

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\text{.}\)

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

For the other side of the equation, let's consider the subset that contains the element \(n\text{,}\) and call the cardinality of this subset \(k\text{.}\) Since \(n\) is in this subset, \(k \ge 1\text{,}\) and since this is a subset of \(\{1, \ldots, n\}\text{,}\) we have \(k \le n\text{,}\) so \(1 \le k \le n\text{.}\) There are \(\binom{n-1}{k-1}\) ways to choose the remaining \(k-1\) elements of this subset; that is, for any \(1 \le k \le n\text{,}\) there are \(\binom{n-1}{k-1}\) ways to choose the subset of \(\{1, \ldots n\}\) that contains the element \(n\text{.}\) 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\text{,}\) 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

\begin{gather*} B_n=\sum_{k=1}^n \binom{n-1}{k-1}B_{n-k}\text{.} \end{gather*}
⬛

Let us try to find the exponential generating function for the Bell numbers. To understand the calculations that follow, you will need to know some calculus (more specifically, you will need to have some background in derivatives). If you don't have that background, you won't understand the details we'll be going over, although you may still be able to get a general sense of what is going on.

When dealing with exponential generating functions, notice that the derivative of \(x^n/n!\) is

\begin{equation*} \frac{nx^{n-1}}{n!}=\frac{x^{n-1}}{(n-1)!}, \end{equation*}

so taking derivatives often helps us find a nice expression for the coefficients. You already know a particularly simple example of this: the derivative of \(e^x\) is \(e^x\text{,}\) which tells us that all of the coefficients in that exponential generating function are equal.

Define

\begin{equation*} B(x)=\sum_{i=0}^\infty B_i\frac{x^i}{i!} = B_0 +B_1\frac{x}{1!}+B_2 \frac{x^2}{2!}+\ldots+B_n\frac{x^n}{n!}+\ldots\text{.} \end{equation*}

Notice that the derivative of this is

\begin{align*} \frac{d}{dx}B(x)\amp= B_1+B_2\frac{x}{1!}+B_3\frac{x^2}{2!}+\ldots+B_n\frac{x^{n-1}}{(n-1)!}+\ldots\\ \amp= \sum_{n=1}^\infty B_n\frac{x^{n-1}}{(n-1)!}\text{.} \end{align*}

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

\begin{align*} \frac{d}{dx}B(x)\amp= \sum_{n=1}^\infty \left[\sum_{k=1}^n \binom{n-1}{k-1}B_{n-k}\right]\frac{x^{n-1}}{(n-1)!}\\ \amp= \sum_{n=1}^\infty \left[\sum_{k=1}^n \frac{(n-1)!}{(k-1)!(n-k)!}B_{n-k}\frac{x^{n-1}}{(n-1)!}\right]\\ \amp= \sum_{n=1}^\infty \left[\sum_{k=1}^n \frac{1}{(k-1)!(n-k)!}B_{n-k}x^{n-1}\right]\\ \amp= \sum_{n=1}^\infty \left[\sum_{k=1}^n \frac{x^{k-1}}{(k-1)!}B_{n-k}\frac{x^{n-k}}{(n-k)!}\right]\text{.} \end{align*}

Notice that for each value of \(n\text{,}\) 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\text{.}\) 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{align*} \frac{d}{dx}B(x)\amp= \sum_{j=0}^\infty \left[\sum_{i=0}^\infty \frac{x^j}{j!}B_i\frac{x^i}{i!}\right]\\ \amp= \sum_{j=0}^\infty \frac{x^j}{j!}\left[\sum_{i=0}^\infty B_i\frac{x^i}{i!}\right]\\ \amp= \left[\sum_{j=0}^\infty \frac{x^j}{j!}\right]\left[\sum_{i=0}^\infty B_i\frac{x^i}{i!}\right]\\ \amp= e^xB(x)\text{.} \end{align*}

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

\begin{equation*} e^{-(e^x)}e^xB(x)-B(x)e^{-(e^x)}e^x=0\text{,} \end{equation*}

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

Since

\begin{equation*} B(0)=\sum_{n=0}^\infty B_n\frac{0^n}{n!}=1+\sum_{n=1}^\infty 0 =1\text{,} \end{equation*}

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

\begin{equation*} ce^{e^0}=ce^1=ce=1\text{,} \end{equation*}

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

\begin{equation*} B(x)=e^{-1}e^{(e^x)}=e^{(e^x-1)}\text{.} \end{equation*}

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

  1. Find \(B_4\text{.}\)

  2. What is the exponential generating function for the sequence \(a_i=i!\) for every \(i \ge 0\text{?}\) Give the sequence in both an expanded and a closed form.

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