Bell numbers (thing)

The Bell numbers, named for mathematician and historian Eric Temple Bell, are used in the theory of partitions and also in the greater area of combinatorics. The n^th Bell number B(n) represents the number of ways a set of distinguishable elements can be partitioned into subsets, all of which contain at least one element. The first few Bell numbers are 1, 1, 2, 5, 15, 52.

As an example, when n = 4, the set containing elements A, B, C, and D can be partitioned as follows, and where one can see that B(4) = 15:

One subset:  1 way
   ABCD
Two subsets: 7 ways
   A   |  BCD
   B   |  ACD
   C   |  ABD
   D   |  ABC
   AB  |  CD
   AC  |  BD
   AD  |  BC
Three subsets: 6 ways
   A  |  B  |  CD
   A  |  C  |  BD
   A  |  D  |  BC
   B  |  C  |  AD
   B  |  D  |  AC
   C  |  D  |  AB
Four subsets: 1 way
   A  |  B  |  C  |  D

Bell numbers can be computed recursively using the Bell triangle, shown below. Given that B(0) = 1, then every successive row has an additional element. The first element of the row is the last element of the previous row, and every other element is the sum of the element to the left of it plus the element above it. The Bell number of the nth row is the first element of the row. (I think this is pretty clever!)

   n     B(n)  -------------------------- Bell Triangle -------------------------------------- 
   0       1                                                                                 1
   1       1                                                                        1        2
   2       2                                                                2       3        5
   3       5                                                        5       7      10       15
   4      15                                               15      20      27      37       52 
   5      52                                       52      67      87     114     151      203
   6     203                              203     255     322     409     523     674      877
   7     877                      877	1,080   1,335   1,654   2,066   2,589   3,263    4,140
   8   4,140            4,140   5,017   6,097   7,432   9,089  11,155  13,744  17,007   21,147
   9  21,147   21,147  25,287  30,304  36,401  43,833  52,922  64,077  77,821  94,828  115,975

Eric Temple Bell (1883-1960) was a Scottish born mathematician who worked in number theory and combinatorics. He was a professor at the University of Washington and later on at CalTech. He's best known for his biographies of mathematicians, "Men of Mathematics". I read this book in college, and found it inspiring. He wrote not just of the men's lives (for they were all men), but of their mathematics, and I found each story engrossing for the subtle way the author built up a curiosity about the central problems the mathematicians faced - and then how they solved them. He was by some accounts a curmudgeon; this certainly came across in his writings.

References

1. Wikipedia, "Bell Number"
2. Eric Weisstein, "Bell Number", Wolfram's Mathworld
3. Paul Bellew, "Bell's Numbers"
4. Handbook of Integer Sequences, Bell or exponential numbers
5. Wikipedia, "Eric Temple Bell"