janmr blog

Bell Numbers

I recently studied a system of linear ODEs, where parameters, described the system. It turned out that the structure of the solutions depended on whether any of the parameters where equal to each other. For instance, with three parameters there were five possibilities:

  1. ,
  2. ,
  3. ,
  4. , ,

We can quickly go through small values of and we get (starting with ): 1, 1, 2, 5, 15, …. How do we obtain a general formula? Observe first that the number of possibilities corresponds to the number of equivalence relations in a set of elements. We can then list the equivalence classes for each possible equivalence relation. For the example we get, corresponding to the list above:

So the number of possibilities also corresponds to the number of partitions of a set of elements. Actually, there are many ways to interpret these numbers, see, e.g., the comments for sequence A000110 at OEIS.

These numbers are typically called Bell Numbers and we will denote them by . We thus have , , .

How can we derive a formula for ? Let us assume we already know and consider the number of partitions of the set . For each partition we will focus on the subset that contains one particular element, say the element .

How many partitions have as a separate subset, i.e., are of the form ? Exactly , as that is the number of partitions of .

How many partitions have as a separate subset, i.e., are of the form ? Well, there are ways of choosing and for each of these, there are ways of partitioning . Thus, there are ways.

How many partitions have as a separate subset, i.e., are of the form ? Well, there are ways of choosing and and for each of these, there are ways of partitioning . Thus, there are ways.

And so on. We get that

for and using we can now compute for any value of (no closed-form expression is known).

Bell numbers are closely related to Stirling numbers of the second kind, see, e.g., my previous post Twelve Ways of Counting.

The excellent books The Book of Numbers and Concrete Mathematics have more information on Bell numbers.