janmr blog

Bell Numbers

I recently studied a system of linear ODEs, where nn parameters, k1,,knk_1, \ldots, k_n 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. k1=k2=k3k_1 = k_2 = k_3
  2. k1=k2k_1 = k_2, k1k3k_1 \neq k_3
  3. k1=k3k_1 = k_3, k1k2k_1 \neq k_2
  4. k2=k3k_2 = k_3, k1k2k_1 \neq k_2
  5. k1k2k_1 \neq k_2, k1k3k_1 \neq k_3, k2k3k_2 \neq k_3

We can quickly go through small values of nn and we get (starting with n=0n=0): 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 nn elements. We can then list the equivalence classes for each possible equivalence relation. For the example n=3n=3 we get, corresponding to the list above:

  1. {{k1,k2,k3}}\{\{k_1,k_2,k_3\}\}
  2. {{k1,k2},{k3}}\{\{k_1,k_2\}, \{k_3\}\}
  3. {{k1,k3},{k2}}\{\{k_1,k_3\}, \{k_2\}\}
  4. {{k2,k3},{k1}}\{\{k_2,k_3\}, \{k_1\}\}
  5. {{k1},{k2},{k3}}\{\{k_1\}, \{k_2\}, \{k_3\}\}

So the number of possibilities also corresponds to the number of partitions of a set of nn 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 BnB_n. We thus have B0=B1=1B_0 = B_1 = 1, B2=2B_2 = 2, B3=5B_3 = 5.

How can we derive a formula for BnB_n? Let us assume we already know B0,,Bn1B_0, \ldots, B_{n-1} and consider the number of partitions of the set Sn={1,2,,n}S_n=\{1,2,\ldots,n\}. For each partition we will focus on the subset that contains one particular element, say the element nn.

How many partitions have {n}\{n\} as a separate subset, i.e., are of the form {{n},}\{\{n\}, \ldots \}? Exactly Bn1B_{n-1}, as that is the number of partitions of Sn{n}S_n - \{n\}.

How many partitions have {n,a}\{n,a\} as a separate subset, i.e., are of the form {{n,a},}\{\{n,a\}, \ldots \}? Well, there are (n11)n-1 \choose 1 ways of choosing aa and for each of these, there are Bn2B_{n-2} ways of partitioning Sn{n,a}S_n - \{n,a\}. Thus, there are (n11)Bn2{n-1 \choose 1} B_{n-2} ways.

How many partitions have {n,a,b}\{n,a,b\} as a separate subset, i.e., are of the form {{n,a,b},}\{\{n,a,b\}, \ldots \}? Well, there are (n12)n-1 \choose 2 ways of choosing aa and bb and for each of these, there are Bn3B_{n-3} ways of partitioning Sn{n,a,b}S_n - \{n,a,b\}. Thus, there are (n12)Bn3{n-1 \choose 2} B_{n-3} ways.

And so on. We get that

Bn=k=0n1(n1k)Bn1k=k=0n1(n1n1k)Bn1k=k=0n1(n1k)BkB_n = \sum_{k=0}^{n-1} {n-1 \choose k} B_{n-1-k} = \sum_{k=0}^{n-1} {n-1 \choose n-1-k} B_{n-1-k} = \sum_{k=0}^{n-1} {n-1 \choose k} B_k

for n1n \geq 1 and using B0=1B_0 = 1 we can now compute BnB_n for any value of nn (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.