We begin with a definition:
Definition 1.4.1 A partition of a set $S$ is a collection of non-empty subsets $A_i\subseteq S$, $1\le i\le k$ (the parts of the partition), such that $\bigcup_{i=1}^k A_i=S$ and for every $i\not=j$, $A_i\cap A_j=\emptyset$. $\square$
Example 1.4.2 The partitions of the set $\{a,b,c\}$ are $\{\{a\},\{b\},\{c\}\}$, $\{\{a,b\},\{c\}\}$, $\{\{a,c\},\{b\}\}$, $\{\{b,c\},\{a\}\}$, and $\{\{a,b,c\}\}$. $\square$
Partitions arise in a number of areas of mathematics. For example, if $\equiv$ is an equivalence relation on a set $S$, the equivalence classes of $\equiv$ form a partition of $S$. Here we consider the number of partitions of a finite set $S$, which we might as well take to be $[n]=\{1,2,3,\ldots,n\}$, unless some other set is of interest. We denote the number of partitions of an $n$-element set by $B_n$; these are the Bell numbers. From the example above, we see that $B_3=5$. For convenience we let $B_0=1$. It is quite easy to see that $B_1=1$ and $B_2=2$.
There are no known simple formulas for $B_n$, so we content ourselves with a recurrence relation.
Theorem 1.4.3 The Bell numbers satisfy $$ B_{n+1} = \sum_{k=0}^n {n\choose k} B_k. $$
Proof. Consider a partition of $S=\{1,2,\ldots,n+1\}$, $A_1$,…,$A_m$. We may suppose that $n+1$ is in $A_1$, and that $|A_1|=k+1$, for some $k$, $0\le k\le n$. Then $A_2$,…,$A_{m}$ form a partition of the remaining $n-k$ elements of $S$, that is, of $S\backslash A_1$. There are $B_{n-k}$ partitions of this set, so there are $B_{n-k}$ partitions of $S$ in which one part is the set $A_1$. There are ${n\choose k}$ sets of size $k+1$ containing $n+1$, so the total number of partitions of $S$ in which $n+1$ is in a set of size $k+1$ is ${n\choose k}B_{n-k}$. Adding up over all possible values of $k$, this means $$ \eqalignno{ B_{n+1} &= \sum_{k=0}^n {n\choose k} B_{n-k}.& (1.4.1)\cr } $$ We may rewrite this, using theorem 1.3.3, as $$ B_{n+1} = \sum_{k=0}^n {n\choose n-k} B_{n-k}, $$ and then notice that this is the same as the sum $$ B_{n+1} = \sum_{k=0}^n {n\choose k} B_k, $$ written backwards. $\qed$
Example 1.4.4 We apply the recurrence to compute the first few Bell numbers: $$ \eqalign{ B_1&=\sum_{k=0}^0 {0\choose 0}B_0 = 1\cdot 1 = 1\cr B_2&=\sum_{k=0}^1 {1\choose k}B_k = {1\choose 0}B_0 + {1\choose 1}B_1 = 1\cdot 1+1\cdot 1 =1+1 =2\cr B_3&=\sum_{k=0}^2 {2\choose k}B_k = 1\cdot 1 + 2\cdot 1 + 1\cdot 2 = 5\cr B_4&=\sum_{k=0}^3 {3\choose k}B_k = 1\cdot 1 + 3\cdot 1 + 3\cdot 2 + 1\cdot 5 = 15\cr } $$ $\square$
The Bell numbers grow exponentially fast; the first few are 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437.
The Bell numbers turn up in many other problems; here is an interesting example. A common need in some computer programs is to generate a random permutation of $1,2,3,\ldots,n$, which we may think of as a shuffle of the numbers, visualized as numbered cards in a deck. Here is an attractive method that is easy to program: Start with the numbers in order, then at each step, remove one number at random (this is easy in most programming languages) and put it at the front of the list of numbers. (Viewed as a shuffle of a deck of cards, this corresponds to removing a card and putting it on the top of the deck.) How many times should we do this? There is no magic number, but it certainly should not be small relative to the size of $n$. Let's choose $n$ as the number of steps.
We can write such a shuffle as a list of $n$ integers, $(m_1,m_2,\ldots,m_n)$. This indicates that at step $i$, the number $m_i$ is moved to the front.
Example 1.4.5 Let's follow the shuffle $(3,2,2,4,1)$: $$ \eqalign{ (3)&:\quad 3 1 2 4 5\cr (2)&:\quad 2 3 1 4 5\cr (2)&:\quad 2 3 1 4 5\cr (4)&:\quad 4 2 3 1 5\cr (1)&:\quad 1 4 2 3 5\cr } $$ $\square$
Note that we allow "do nothing'' moves, removing the top card and then placing it on top. The number of possible shuffles is then easy to count: there are $n$ choices for the card to remove, and this is repeated $n$ times, so the total number is $n^n$. (If we continue a shuffle for $m$ steps, the number of shuffles is $n^m$.) Since there are only $n!$ different permutations of $1,2,\ldots,n$, this means that many shuffles give the same final order.
Here's our question: how many shuffles result in the original order?
Example 1.4.6 These shuffles return to the original order: $(1,1,1,1,1)$, $(5,4,3,2,1)$, $(4,1,3,2,1)$. $\square$
Theorem 1.4.7 The number of shuffles of $[n]$ that result in the original sorted order is $B_n$.
Proof. Since we know that $B_n$ counts the number of partitions of $\{1,2,3,\ldots,n\}$, we can prove the theorem by establishing a 1–1 correspondence between the shuffles that leave the deck sorted and the partitions. Given a shuffle $(m_1,m_2,\ldots,m_n)$, we put into a single set all $i$ such that $m_i$ has a single value. For example, using the shuffle $(4,1,3,2,1)$, Since $m_2=m_5$, one set is $\{2,5\}$. All the other values are distinct, so the other sets in the partition are $\{1\}$, $\{3\}$, and $\{4\}$.
Note that every shuffle, no matter what the final order, produces a partition by this method. We are only interested in the shuffles that leave the deck sorted. What we now need is to show that each partition results from exactly one such shuffle.
Suppose we have a partition with $k$ parts. If a shuffle leaves the deck sorted, the last entry, $m_n$, must be 1. If the part containing $n$ is $A_1$, then it must be that $m_i=1$ if and only if $i\in A_1$. If $k=1$, then the only part contains all of $\{1,2,\ldots,n\}$, and the shuffle must be $(1,1,1,\ldots,1)$.
If $k>1$, the last move that is not 1 must be 2, since 2 must end up immediately after 1. Thus, if $j_2$ is the largest index such that $j_2\notin A_1$, let $A_2$ be the part containing $j_2$, and it must be that $m_i=2$ if and only if $i\in A_2$. We continue in this way: Once we have discovered which of the $m_i$ must have values $1,2,\ldots,p$, let $j_{p+1}$ be the largest index such that $j_{p+1}\notin A_1\cup\cdots\cup A_p$, let $A_{p+1}$ be the part containing $j_{p+1}$, and then $m_i=p+1$ if and only if $i\in A_{p+1}$. When $p=k$, all values $m_i$ have been determined, and this is the unique shuffle that corresponds to the partition. $\qed$
Example 1.4.8 Consider the partition $\{\{1,5\},\{2,3,6\},\{4,7\}\}$. We must have $m_7=m_4=1$, $m_6=m_3=m_2=2$, and $m_5=m_1=3$, so the shuffle is $(3,2,2,1,3,2,1)$. $\square$
Returning to the problem of writing a computer program to generate a partition: is this a good method? When we say we want a random permutation, we mean that we want each permutation to occur with equal probability, namely, $1/n!$. Since the original order is one of the permutations, we want the number of shuffles that produce it to be exactly $n^n/n!$, but $n!$ does not divide $n^n$, so this is impossible. The probability of getting the original permutation is $B_n/n^n$, and this turns out to be quite a bit larger than $1/n!$. Thus, this is not a suitable method for generating random permutations.
The recurrence relation above is a somewhat cumbersome way to compute the Bell numbers. Another way to compute them is with a different recurrence, expressed in the Bell triangle, whose construction is similar to that of Pascal's triangle: $$\matrix{ A_{1,1}\cr A_{2,1}&A_{2,2}\cr A_{3,1}&A_{3,2}&A_{3,3}\cr A_{4,1}&A_{4,2}&A_{4,3}&A_{4,4}\cr} \qquad\matrix{ 1\cr 1&2\cr 2&3&5\cr 5&7&10&15\cr} $$ The rule for constructing this triangle is: $A_{1,1}=1$; the first entry in each row is the last entry in the previous row; other entries are $A_{n,k}=A_{n,k-1}+A_{n-1,k-1}$; row $n$ has $n$ entries. Both the first column and the diagonal consist of the Bell numbers, with $A_{n,1}=B_{n-1}$ and $A_{n,n}=B_n$.
$A_{n,k}$ may be interpreted as the number of partitions of $\{1,2,\ldots,n+1\}$ in which $\{k+1\}$ is the singleton set with the largest entry in the partition. For example, $A_{3,2}=3$; the partitions of $3+1=4$ in which $2+1=3$ is the largest number appearing in a singleton set are $\{\{1\},\{2,4\},\{3\}\}$, $\{\{2\},\{1,4\},\{3\}\}$, and $\{\{1,2,4\},\{3\}\}$.
To see that this indeed works as advertised, we need to confirm a few things. First, consider $A_{n,n}$, the number of partitions of $\{1,2,\ldots,n+1\}$ in which $\{n+1\}$ is the singleton set with the largest entry in the partition. Since $n+1$ is the largest element of the set, all partitions containing the singleton $\{n+1\}$ satisfy the requirement, and so the $B_n$ partitions of $\{1,2,\ldots,n\}$ together with $\{n+1\}$ are exactly the partitions of interest, that is, $A_{n,n}=B_n$.
Next, we verify that under the desired interpretation, it is indeed true that $A_{n,k}=A_{n,k-1}+A_{n-1,k-1}$ for $k>1$. Consider a partition counted by $A_{n,k-1}$. This contains the singleton $\{k\}$, and the element $k+1$ is not in a singleton. If we interchange $k$ and $k+1$, we get the singleton $\{k+1\}$, and no larger element is in a singleton. This gives us partitions in which $\{k+1\}$ is a singleton and $\{k\}$ is not. Now consider a partition of $\{1,2,\ldots,n\}$ counted by $A_{n-1,k-1}$. Replace all numbers $j>k$ by $j+1$, and add the singleton $\{k+1\}$. This produces a partition in which both $\{k+1\}$ and $\{k\}$ appear. In fact, we have described how to produce each partition counted by $A_{n,k}$ exactly once, and so $A_{n,k}=A_{n,k-1}+A_{n-1,k-1}$.
Finally, we need to verify that $A_{n,1}=B_{n-1}$; we establish a bijection between the two sets. Suppose a partition in $A_{n,1}$ has the form $\{\{1\},\{2\},X_1,X_2,\ldots,X_k\}$, where no $X_i$ is a singleton. Then the collection $\{X_1,X_2,\ldots,X_k\}$ is a partition of the $n-1$ element set $\{3,4,\ldots, n+1\}$. Now we subtract 2 from every element to get a partition of $[n-1]$ that has no singleton sets. Any other partition in $A_{n,1}$ has the form $\{\{2\},X_1,X_2,\ldots,X_k\}$, where no $X_i$ is a singleton. One of the sets $X_i$ contains $n+1$, say $X_1$. Remove $n+1$ and split the remainder of $X_1$ into singleton sets $\{x_1\}, \{x_2\},\ldots, \{x_m\}$. Now $\{\{x_1\}, \{x_2\},\ldots, \{x_m\},X_2,X_3,\ldots,X_k\}$ is a partition of the $n-1$ element set $\{1,3,\ldots,n\}$. Subtracting one from all the elements except 1 produces a partition of $[n-1]$ with at least one singleton set. If $p\in A_{n,1}$, designate the partition of $[n-1]$ obtained in this way by $f(p)$.
Now we define a function $g$ from $B_{n-1}$ to $A_{n,1}$. If partition $p\in B_{n-1}$ contains no singletons, say $p=\{X_1,\ldots,X_k\}$, add two to every element forming sets $X_i^*$, and let $g(p)=\{\{1\},\{2\},X_1^*,\ldots,X_k^*\}$. If $p$ contains singletons, say $p=\{\{x_1\}, \{x_2\},\ldots, \{x_m\},X_2,X_3,\ldots,X_k\}$, then add 1 to all elements except 1, forming a partition $\{\{x_1^*\}, \{x_2^*\},\ldots, \{x_m^*\},X_2^*,X_3^*,\ldots,X_k^*\}$ of the set $\{1,3,\ldots,n\}$. Now let $g(p)=\{\{2\},\{x_1^*,x_2^*,\ldots,x_m^*,n+1\},X_2^*,\ldots,X_k^*\}$.
Since $f(g(p))=p$ and $g(f(p))=p$, $f$ and $g$ are inverses and so $f$ is a bijection between $A_{n,1}$ and $B_{n-1}$, as desired.
Exercises 1.4
Ex 1.4.1 Show that if $\{A_1,A_2,\ldots,A_k\}$ is a partition of $\{1,2,\ldots,n\}$, then there is a unique equivalence relation $\equiv$ whose equivalence classes are $\{A_1,A_2,\ldots,A_k\}$.
Ex 1.4.2 Suppose $n$ is a square-free number, that is, no number $m^2$ divides $n$; put another way, square-free numbers are products of distinct prime factors, that is, $n=p_1p_2\cdots p_k$, where each $p_i$ is prime and no two prime factors are equal. Find the number of factorizations of $n$. For example, $30=2\cdot 3\cdot 5$, and the factorizations of 30 are 30, $6\cdot 5$, $10\cdot 3$, $2\cdot 15$, and $2\cdot 3\cdot 5$. Note we count 30 alone as a factorization, though in some sense a trivial factorization.
Ex 1.4.3 The rhyme scheme of a stanza of poetry indicates which lines rhyme. This is usually expressed in the form ABAB, meaning the first and third lines of a four line stanza rhyme, as do the second and fourth, or ABCB, meaning only lines two and four rhyme, and so on. A limerick is a five line poem with rhyming scheme AABBA. How many different rhyme schemes are possible for an $n$ line stanza? To avoid duplicate patterns, we only allow a new letter into the pattern when all previous letters have been used to the left of the new one. For example, ACBA is not allowed, since when C is placed in position 2, B has not been used to the left. This is the same rhyme scheme as ABCA, which is allowed.
Ex 1.4.4 Another way to express the Bell numbers for $n>0$ is $$ B_n=\sum_{k=1}^n S(n,k), $$ where $S(n,k)$ is the number of partitions of $\{1,2,\ldots,n\}$ into exactly $k$ parts, $1\le k\le n$. The $S(n,k)$ are the Stirling numbers of the second kind. Find a recurrence relation for $S(n,k)$. Your recurrence should allow a fairly simple triangle construction containing the values $S(n,k)$, and then the Bell numbers may be computed by summing the rows of this triangle. Show the first five rows of the triangle, $n\in\{1,2,\ldots,5\}$.
Ex 1.4.5 Let $A_n$ be the number of partitions of $\{1,2,\ldots,n+1\}$ in which no consecutive integers are in the same part of the partition. For example, when $n=3$ these partitions are $\{\{1\},\{2\},\{3\},\{4\}\}$, $\{\{1\},\{2,4\},\{3\}\}$, $\{\{1,3\},\{2\},\{4\}\}$, $\{\{1,3\},\{2,4\}\}$, $\{\{1,4\},\{2\},\{3\}\}$, so $A_3=5$. Let $A(n,k)$ be the number of partitions of $\{1,2,\ldots,n+1\}$ into exactly $k$ parts, in which no consecutive integers are in the same part of the partition. Thus $$ A_n=\sum_{k=2}^{n+1} A(n,k). $$ Find a recurrence for $A(n,k)$ and then show that $A_n=B_n$.