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 nth 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
- Wikipedia, "Bell Number"
- Eric Weisstein, "Bell Number", Wolfram's Mathworld
- Paul Bellew, "Bell's Numbers"
- Handbook of Integer Sequences, Bell or exponential numbers
- Wikipedia, "Eric Temple Bell"