Bell Numbers

My tweet for today's numbers was:

24556: 2^2×7×877 with 877 member of OEIS A000110: Bell or exponential numbers, number of ways to partition a set of n labeled elements (n=7)

I had to check on exactly what a Bell number was of course and the Wikipedia entry states:

In combinatorial mathematics, the Bell numbers count the number of partitions of a set. These numbers have been studied by mathematicians since the 19th century, and their roots go back to medieval Japan, but they are named after Eric Temple Bell, who wrote about them in the 1930s. 

Starting with \(B_0\) = \(B_1\) = 1, the first few Bell numbers are: 

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057, ... (sequence A000110 in OEIS). 

The nth of these numbers \(B_n\) counts the number of different ways to partition a set that has exactly n elements, or equivalently, the number of equivalence relations on it. Outside of mathematics, the same number also counts the number of different rhyme schemes for n-line poems. 

As well as appearing in counting problems, these numbers have a different interpretation, as moments of probability distributions. In particular, \(B_n\) is the \(n\)-th moment of a Poisson distribution with mean 1.

The sequence of Bell numbers can be constructed as shown below and the format is analogous to Pascal's Triangle:

 1

 1     2

  2     3     5

   5     7    10    15

   15    20    27    37    52

    52    67    87   114   151   203

    203   255   322   409   523   674   877 

ADDENDUM: reading over this again on 6th February 2019, I was a little confused so I've added the following information (taken from this source) to clarify any possible confusion:

Bell’s Numbers: What they Are and What they Mean

The first Bell numbers are:

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975.

The \(n\)-th Bell number, \(B_n\), is the number of nonempty subsets a set of size \(n\) can be partitioned into. \(B_0\) is defined as one (i.e. the first number in the above list); There is just one possible partition of the set containing one member, so \(B_1\) = 1.

There are two partitions possible for a set with two elements, so \(B_2\) is just two.

A set with three elements can be partitioned five ways. Taking the set {a, b, c}, the five possible partitions are:

{(a) (b) (c)}, {(a, b), (c)}, {(a, c) (b)}, {(b, c), a}, {(a, b, c)}

There isn’t any simple formula that can give us \(B_n\), but we can find Bell’s numbers in the Bell Triangle, in the next section, or use the following recursive equation to define them:

Bell’s Numbers and the Bell Triangle as a Way to Derive them

The Bell triangle is an easy-to-fill in right triangle which gives us, in the left hand column, all of the Bell numbers.

1. Creating the Triangle

You make the triangle this way:

• On row one, write the number 1
• Begin all other rows with the last number of the previous row. The last number in row 1 was 1, so row 2 also begins with 1.
• All other numbers are found by adding the last number to the one above it. To find out what to write in the second place in row 2, we look at the place before it, place 1. This is just 1, and the digit 1 is above it, so 1 + 1 = 2

The first part of the Bell triangle will therefore be

1

1 2

Following those same rules, we begin the third row with the last number in the previous row, or 2. Then we add that 2 to the number above it to find the next number is 3. Three plus the two above it makes five, so the row finishes with a five.

1

1 2

2 3 5

Row four starts with the last of row three, i.e., 5. Then 5 + 2 = 7, so the next place is 7, and 7 + 3 = 10, so the next digit is ten. Finishing this row and the next in the same manner, we get

1

1 2

2 3 5

5 7 10 15

15 20 27 37 52

For any row \(k\), the number that starts the row is \(B_{k-1}\). So the first digit of row 1 is \(B_{1 -1} = B_0\), the first digit of row 4 is \(B_3\), and the first digit of row 55 will be \(B_{54} \).

2. Reading the Triangle

The Bell numbers are given by the far left column, bolded here:

1

1 2

2 3 5

5 7 10 15

15 20 27 37 52

Note that the triangle is sometimes mirrored, so Bell’s numbers appear in the right column, and not the left; Make sure you know the construction of the triangle before attempting to read it.