Bell number

The Bell numberDlmfMathworldPlanetmath, denoted B(n) is the total number of partitionsMathworldPlanetmath of a set with n elements. For n=0, we have B(0)=1. For n1, we have

B(n)=k=0nS(n,k)  for n1

where S(n,k) are the Stirling numbers of the second kind.

Proposition 1.

We count the number of partitions of a set of n+1 elements, depending on the size of the block containing the n+1st element. If the block has size j for 1jn+1 then we have (nj-1) choices for the j-1 other elements of the block. The remaining n+1-j elements can be partitioned in B(n+1-j) ways. We have therefore that:

B(n+1) = j=1n+1(nj-1)B(n+1-j)
= j=1n+1(nn+1-j)B(n+1-j)
= k=0n(nk)B(k)

Using the formula above, one can easily derive the first few Bell numbers. Starting with n=0, the first ten Bell numbers are 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147.

Title Bell number
Canonical name BellNumber
Date of creation 2013-03-22 14:47:07
Last modified on 2013-03-22 14:47:07
Owner aoh45 (5079)
Last modified by aoh45 (5079)
Numerical id 7
Author aoh45 (5079)
Entry type Definition
Classification msc 05A18
Classification msc 11B73
Related topic StirlingNumbersSecondKind