More Discrete Mathematicsvia Graph Theory

Section3.5Bell Numbers

The Bell number, \(B_{k}\text{,}\) denotes the number of ways that a set of \(k\) objects can be partitioned into nonempty subsets. We have already seen how to partition a set of \(k\) objects into exactly \(n\) subsets: \(S(k,n)\text{.}\) So on its face, \(B_k = \sum_{n=1}^kS(k,n)\text{.}\)

The sequence of Bell numbers starts

Notice that the first four numbers look like Catalan numbers. In fact, one of the many things the Catalan numbers count are non-intersecting set partitions. Once you believe this, you see that \(C_n \le B_n\) for all \(n\text{.}\)

The Bell numbers can be generated by constructing what is called the Bell Triangle. To construct this triangle, begin with a 1 at the top and a 1 below it. Add these two numbers together and put the sum 2, to the right of the 1 in the second column. This 2 is also the first entry of the third row. The second entry in the third row is found by adding the 2 to the number 1 above it. This sum is 3 and goes to the right of the 2. The 3 is now below a 2. Adding these two numbers produces the last number, 5, in the third row. Since 5 has no number above it, the third row is complete. 5 now becomes the first number in the fourth row and the process continues.

To summarize, construction of the triangle follows two basic rules:

1. The last number of each row is the first number of the next row.

2. All other numbers are found by adding the number to the left of the missing number to the number directly above this same number.

When the triangle is extended, as above, the Bell Numbers are found down the first column as well as along the outside diagonal.

As with Pascal's Triangle, the Bell triangle has several interesting properties.

Rotating the triangle slightly creates a difference triangle analogous to Pascal's Triangle. The entries that are formed recursively by adding in Pascal's Triangle are now differences of the two numbers above them in the Bell triangle.

Finally, rewriting the Bell triangle recursively indicates a nice connection of the Bell Numbers to Pascal's triangle.

This pattern suggests the \({(n + 1)}^{\text{th}}\) Bell Number can be represented recursively by \(B_{n + 1} = \binom{n}{0} B_{0} + \binom{n}{1} B_{1} + \binom{n}{2}B_{2} + \ldots + \binom{n}{n} B_{n}\text{.}\) The coefficients of this equation are the entries of the \(n\)th row of Pascal's triangle.

The Bell numbers are related to the Stirling numbers and can be defined as the sum of the Stirling numbers of the second kind. That is, \(B_{k} = S(k,1) + S(k,2) + \cdots + S(k,k)\text{,}\) where \(S(k,n)\) represents the number of ways of grouping \(k\) elements into \(n\) subsets. So \(B_{3} = S(3,1) + S(3,2) + S(3,3) = 1 + 3 + 1 = 5\text{.}\) Since the Bell numbers count the partitions of a set of elements, they are used in prime-number theory to enumerate the number of ways to factor a number with distinct prime factors. For example, 42 has three distinct prime factors: 2, 3, and 7. Since \(B_{3} = 5\) , we know there are five ways of factoring 42. These are \(2 \times 3 \times 7\text{,}\) \(2 \times 21\text{,}\) \(3 \times 14\text{,}\) \(6 \times 7\text{,}\) and \(42\text{.}\) So the number \(210\text{,}\) which has 4 distinct factors, 2, 3, 5, and 7, can be factored in \(B_{4} = 15\) ways.

The Bell numbers can be used to model many real-life situations. For example, the number of different ways two people can sleep in unlabeled twin beds is \(B_{2} = 2\) ways: They can sleep in the same bed or in separate beds. The number of ways of serving a dinner consisting of three items, such as a salad, bread, and fish is \(B_{3} = 5\) ways: each could be served on a separate plate, salad and bread could be on one plate and fish on another, salad and fish on one plate and bread on another, or all three items could be on the same plate. This example serves as a model for the five ways three people can occupy three unlabeled beds, the five ways three prisoners can be handcuffed together, the five ways three nations can be form alliances, or any situation of partitioning three distinct elements into non-empty subsets.

One interesting application of Bell numbers is in counting the number of rhyme schemes possible for a stanza in poetry. There are \(B_{2} = 2\) possibilities for a two-line stanza: the lines can either rhyme or not rhyme. The possible rhyme schemes of a three-line stanza can be described as aaa, aab, aba, abb, and abc: thus there are 5 or \(B_{3}\) possible rhyme schemes. The Japanese used diagrams depicting possible rhyme schemes of a five-line stanza \(B_{5} = 52\) as early as 1000 A.D. in the Tale of the Genji by Lady Shikibu Murasaki.

We conclude with an interesting activity.