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?
 A: 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:


*

*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$.

*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}
A: 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}.
$$
A: This is essentially the answer of Austin Mohr, but skipping the step of symmetry. I personally find it easier to remember this way of arguing.

To partition the set $\{0,\dots,n\}$, we proceed as follows:

*

*Decide how many elements $k$ we wish not to be contained in the part of $0$; there are $\binom nk$ options;

*Choose a partition of those $k$ elements; there are $B_k$ options.

Summing over all $k$ gives $B_{n+1}$. Thus $$B_{n+1}=\sum_k\binom nk B_k.$$
A: 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.
