# Bell numbers (number of partitions of set of cardinality n) recurrence relation proof

Let $$X$$ be a set of cardinality $$n$$. How many partitions does it have? The users on the website found that these are the so called bell numbers. They also pointed out the following recurrence relation:

$$B_{n+1}=\sum\limits_{k=0}^n\binom{n}{k}B_k$$

Could someone provide some insight and prove this?

• See the subsection "Counting Partitions" in en.wikipedia.org/wiki/Partition_of_a_set – Lord Soth Jun 28 '13 at 14:56
• I think the function S(n,k) that gives the number of partitions of size k of a set of size n. I don't think S(n,k) has a closed form. The function you are asking about is $\sum_{k=1}^n S(n,k)$ – Amr Jun 28 '13 at 14:57
• @Amr: Those $S(n,k)$ are called Stirling numbers (of the second kind). The sum $B(n):=\sum\limits_{k=0}^{n}S(n,k)$ is called Bell number. – Tomas Jun 28 '13 at 15:01
• @Tomas Thanks. ${}{}{}{}{}$ – Amr Jun 28 '13 at 15:02
• See Gian-Carlo Rota's paper, "The Number of Partitions of a Set", American Mathematical Monthly, volume 71, number 5, May 1964. He derives this identity. Also, I think the Wikipedia article on Bell numbers reproduces that argument. – Michael Hardy Jun 28 '13 at 16:53

For concreteness, let's suppose we are partitioning the set $\{1, 2, \dots, n+1\}$. Focus first on the block containing the element $1$. Let $k$ denote the number of elements other than $1$ that belong to this block. We can choose these elements in $\binom{n}{k}$ ways. Having formed this block, we partition the remaining $n + 1 - (k + 1) = n -k$ elements in $B_{n-k}$ ways. Summing over $k$ gives $$\sum_{k = 0}^n \binom{n}{k} B_{n-k}.$$ By the symmetry of the binomial coefficients, this expression is equivalent to $$\sum_{k = 0}^n \binom{n}{k} B_{k}.$$

I like Austin Mohr's answer. It is precise but a bit dense. Please allow me make it more explicit.

Define $X_n=\{ x_1, \cdots, x_n \}$.

For $n=0$ the empty set has only 1 partition. That is $B_0=1$. With $n=1$, $X_n$ has only one element $X_1=\{x_1\}$ and $B_1=1$. Now $X_{2}$ has two elements. What we need to know is how this new element $x_2$ changes the picture. \begin{equation} X_2 = \{x_1 , x_2 \} = X_1 \cup \{ x_2 \}. \end{equation}

The new element $x_2$ can go in any old subset of the old partition of $X_1$. That is for each of the $B_i$ partitions $i<2$, of $X_1$, $x_2$ can go into it as follows:

1. Join the $\emptyset$. That is \begin{equation} \{ x_2\} \cup \emptyset = \{ x_2 \}, \end{equation} We count this as $1 B_0=\binom{1}{0} B_0$.

2. Join $x_1$. That is \begin{equation} \{ x_1, x_2 \}. \end{equation} We count this as $1 B_1 = \binom{1}{1} B_1$.

\begin{equation} B_2 = \binom{1}0 B_0 + \binom{1}{1} B_1 = 2. \end{equation} Explicitly we have \begin{eqnarray} P_1 &=& \{ \{ x_1 \}, \{ x_2 \} \} \\ P_2 &=& \{ \{x_1, x_2 \} \} . \end{eqnarray} We now assume that we know $B_n$ for the set $X_n$ and construct the set $X_{n+1}$ where the new element $x_{n+1}$ should be added to the set $X_n$. We ask, how this new element $x_{n+1}$ will shake things up.

Given a partition of $X_{n+1}$, the element $x_{n+1}$ should be present in one (and only one) block of this partition. Let us take that block and assume that the block has $k$ elements (no counting the $x_{n+1}$ new element). How many of these block prototypes would we have? We can pick any $k$ out of $n$ elements and this will represent the number of blocks with $k+1$ ( the 1 is for $x_{n+1}$) elements where $x_{n+1}$ is present. This number is $\binom{n}{k}$. We still have to count partitions. Every block of this type corresponds to a partition with $n+1-(k+1)=n-k$ elements. That is for every block of this we have $B_{n-k}$ partitions. The total number of partitions is \begin{equation} \sum_{k=0}^{n} \binom{n}{k} B_{n-k}. \end{equation} Note that if $k=0$, this means that $x_{n+1}$ goes into a singleton $\{x_{n+1}\}$, where $\binom{n}{0}=1$ and we have $B_n$ partitions all without $x_{n+1}$. This happened just before adding $x_{n+1}$. On the other extreme is $k=n$. This means that the block is the whole set $X_n$ and there is no much to play with other than adding the element $x_{n+1}$ to the whole set $X_n$ making it $X_{n+1}$. Note that, since \begin{equation} \binom{n}{k}=\binom{n}{n-k} \end{equation} we can write \begin{equation} \sum_{k=0}^{n} \binom{n}{k} B_{n-k} = \sum_{k=0}^{n} \binom{n}{n-k} B_{n-k} = \sum_{k=n}^{0} \binom{n}{n-k} B_{n-k} = \sum_{k=0}^{n} \binom{n}{k} B_{k}. \end{equation}

See Gian-Carlo Rota's paper, "The Number of Partitions of a Set", American Mathematical Monthly, volume 71, number 5, May 1964. He derives this identity. Also, I think the Wikipedia article on Bell numbers reproduces that argument.

A slight oddity of Rota's paper is that it doesn't even hint that he had any thoughts of probability in mind. He proves "Dobinski's formula", which can be stated as $\mathbb E(X^n)=B_n$ where $X\sim\operatorname{Poisson}(1)$, but he doesn't say anything about it's being a moment of a probability distribution; rather he just says here's an infinite series whose sum is $B_n$. He also states (his formula $(6)$ in the paper) a proposition that, when construed as a statement about the Poisson distribution (with any expected value $>0$, not necessarily $1$), is known as the Robbins lemma, after Herbert Robbins. I think Robbins stated it in his very first paper on empirical Bayes methods in statistics, in about 1955.

Here's another characterization of the Bell numbers, that might be viewed as somewhere between probability and combinatorics. Let a random bijection of $\{1,\ldots,n\}$ be uniformly distributed, i.e. all $n!$ bijections are equally probable. Then the $k$th moment of the probability distribution of the number of fixed points is $B_k$ for $0\le k\le n$. (For $k>n$, if I recall correctly, the $k$th moment is less than $B_k$.) The easy way to prove this, once you've got Dobinski's formula, is by thinking about $\mathbb E(Y(Y-1)(Y-2)\cdots(Y-k+1))$ where $Y$ is the number of fixed points.