Bell Numbers

Figure 1: book cover

I came across an interesting book titled Combinatorics and Number Theory of Counting Sequences by István Mezö and, while most of the content looks intimidating, the author starts off very simply. He certainly gets around as the brief biographical details in Figure 2 reveal. He has a website on Google Sites and interestingly he also has something to say about surreal numbers which I haven't heard anything of since reading Donald Knuth's eponymous book. Well, I started reading it but didn't finish. Maybe this guy can rekindle my interest.

Figure 2: brief biography of author

The first topic he introduces is Bell Numbers, that I've certainly heard about, but never understood. The problem with my current approach to number theory (whereby I look at the mathematical significance of my diurnal age) is that it's rather discursive. I come into contact with a broad range of concepts but don't pursue them in any great depth.

If I could work my way further into this book, I might be able to remedy that. Anyway, I now understand Bell Numbers and I'll try to present what I've found out about them here and hopefully include some practical applications that a little research may throw up. The Bell numbers arise from a simple enough problem. Suppose we have a group of six people that we shall label 1, 2, 3, 4, 5, 6. These six people can make up the set A = {1, 2, 3, 4, 5, 6}. We ask the question: in how many ways can we arrange these six people into groups with no person able to be in more than one group? A group can consist of between one and six members.

Figure 3: I downloaded and collected this group of six characters using SketchUp

The author starts off by looking at small sets. One person can be placed in only one group obviously but two people can be placed into groups in two different ways, either together 1, 2 or separately 1|2. For three people, there are five possibilities:

1, 2, 3 or 1|2, 3 or 2|1, 3 or 3|1, 2 or 1|2|3

These are the first three Bell numbers named after Eric Temple Bell (1883-1960), Scottish mathematician, writer and early science fiction author. Thus:$$B_1=1 \text{ and } B_2=2 \text{ and } B_3=5$$I'll quote directly from the book here and he explains how to derive a general recursive formula for the Bell numbers:

As n grows, it is becoming harder and harder to calculate the Bell numbers by simply listing the partitions, so we must find a simpler way. To do this, we consider the following method. Let us fix an n-set A, and we pick out an arbitrary element a from that of n. If we consider all the partitions of A, there will be n possible cases: the element a is in a block of k elements, where k can be 1, 2, . . . , n. The first possibility, when k = 1, results in the block {a}. When a is in a two-element block, say, in {a, b}, then we have to choose the element b beside a. This can be done in \(n − 1 =  \binom{n-1}{1} \) ways. If a is contained in a block of three elements, then we have to choose two elements beside a on \( \binom{n-2}{2} \) ways. And so on, until arriving k = n: if a is contained in an n-block (i.e., the partition contains one block and this is the whole A), then we have to choose n−1 elements beside a. This is possible just in \( \binom{n-1}{n-1}= 1 \) way. After n−1 fixing the size k of the block of a, we can focus on the remaining elements not in the block of a. We see that the remaining n−k elements can be partitioned arbitrarily and the total number of these partitions is \(B_{n−k} \) by the definition of the Bell numbers. Hence, for any single k there are \( \binom{n-1}{n-k} B_{n-k}\) cases. We can sum up the possible values of k, because these cases are pairwise disjoint. Hence we have:

$$B_n=1 \, . B_{n-1}+\binom{n-1}{1} \,.B_{n-2}+\binom{n-2}{2} \, . B_{n-3} + \dots + \binom{n-1}{n-1} \, . 1$$For consistency in the previous formula, we can replace the initial 1 with \( \binom{n-1}{0}\) and the final 1 with \(B_0=1\). This produces:$$B_n=\binom{n-1}{0} \, . B_{n-1}+\binom{n-1}{1} \,.B_{n-2}+\binom{n-2}{2} \, . B_{n-3} + \dots + \binom{n-1}{n-1} \, . B_0$$This can be written more succinctly as:$$B_n=\sum_{k=0}^{n-1} \binom{n-1}{k} \, .B_{n-k-1}$$Using the fact that \( \binom{n}{k}=\binom{n}{n-k} \) and \( \binom{n-1}{k}=\binom{n-1}{n-1-k} \), we can then write:$$B_n=\sum_{k=0}^{n-1} \binom{n-1}{n-1-k} \, .B_{n-1-k}=\sum_{k=0}^{n-1} \binom{n-1}{k} \, .B_{k}$$The recursive formula on the right enables us to find other Bell numbers. We already know that \(B_0=1, B_1=1, B_2=2 \text{ and } B_3=5 \) and so:$$B_4=\sum_{k=0}^{4-1} \binom{4-1}{k} \, .B_k=\binom{3}{0} \, . B_0+ \binom{3}{1} \, . B_1+\binom{3}{2} \, . B_2+\binom{3}{3} \, . B_3= 15$$Continuing this process, we get \(B_5=52\) and \(B_6=203\) and thus:

Question: in how many ways can we arrange these six people into groups with no person able to be in more than one group?

Answer: 203.

There is however, an easier way to generate the Bell numbers if we don't want to concern ourselves with theoretical justification. It involves use of the so-called Bell triangle, explained by Wikipedia in full but just shown below as it's pretty self-explanatory:

Here are the first five rows of the triangle constructed by these rules: 

 1
 1   2
 2   3   5
 5   7  10  15
15  20  27  37  52 

The Bell numbers appear on both the left and right sides of the triangle.

Mezö's approach to deriving the Bell numbers, as outlined above, involves the use of Stirling numbers of the second kind. These are simply the components of the summation that were obtained from the different values of k. The symbol used is:$$\begin{Bmatrix}
           n \\         
           k \\
          \end{Bmatrix}$$It represents how many groups of k can be formed from n elements. For example, take the case of n=4 and k=2. Suppose A = {a, b, c, d}, then we have the following seven possibilities:

1|2,3,4   2|1,3,4   3|1,2,4   4|1,2,3   1,2|3,4   1,3|2,4   1,4|2,3

$$\text{Thus }\begin{Bmatrix}
           4 \\         
           2 \\
          \end{Bmatrix}=7 \text{ and likewise }\begin{Bmatrix}
           4 \\         
           1 \\
          \end{Bmatrix}=1 \, , \begin{Bmatrix}
           4 \\         
           3 \\
          \end{Bmatrix}=6 \text{ and }\begin{Bmatrix}
           4 \\         
           4 \\
          \end{Bmatrix}=1$$ $$ \text{Thus we can say that } B_n=\begin{Bmatrix}
           n \\         
           1\\
          \end{Bmatrix}+\begin{Bmatrix}
           n \\         
           2 \\
          \end{Bmatrix}+ \cdots +\begin{Bmatrix}
           n \\         
           n \\
          \end{Bmatrix}$$That's as far as I'll pursue the Stirling numbers here but I'd like to now look at some of the practical applications for Bell numbers. Wikipedia provides two examples:

Factorisations

If a number N is a square-free positive integer (meaning that it is the product of some number n of distinct prime numbers), then Bn gives the number of different multiplicative partitions of N. These are factorisations of N into numbers greater than one, treating two factorisations as the same if they have the same factors in a different order. For instance, 30 is the product of the three primes 2, 3, and 5, and has B3 = 5 factorisations:$$30=2\times 15=3\times 10=5\times 6=2\times 3\times 5$$Rhyme schemes

The Bell numbers also count the rhyme schemes of an n-line poem or stanza. A rhyme scheme describes which lines rhyme with each other, and so may be interpreted as a partition of the set of lines into rhyming subsets. Rhyme schemes are usually written as a sequence of Roman letters, one per line, with rhyming lines given the same letter as each other, and with the first lines in each rhyming set labeled in alphabetical order. Thus, the 15 possible four-line rhyme schemes are AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC, and ABCD.

Bell numbers can be prime and thus there are Bell primes. The first few are:$$B_2=2 \, ,B_3=5 \, , B_7=877 \text{ and }B_{13}=27644437$$The indices are prime as well but this is not always the case as the next two indices yielding prime numbers are 42 and 55 (and very large primes they are too). Bell is famous for his somewhat flawed 1937 book "Men of Mathematics" but he also wrote science fiction novels under the name John Taine.

Figure 4: cover of Bell's book

For some interesting biographical details on E. T. Bell, follow this link. There is an interesting comment made in A History of Mathematics: From Mesopotamia to Modernity by Luke Hodgkin (2005):

The fact that Wiles was stimulated in childhood by E. T. Bell's romantic personalized anecdotal book Men of Mathematics to nurse an ambition to solve the problem Fermat's Last Theorem is in itself an index of the power which a certain view of the history of mathematics can exercise.

On page 413 of Combinatorics and Number Theory of Counting Sequences, the author provides a table of the initial Bell numbers. This is shown in Figure 5:

Figure 5: the initial Bell numbers