Digital Library of Mathematical Functions
About the Project
NIST
26 Combinatorial AnalysisProperties

§26.7 Set Partitions: Bell Numbers

Contents

§26.7(i) Definitions

B(n) is the number of partitions of {1,2,,n}. For S(n,k) see §26.8(i).

26.7.1 B(0)=1,
26.7.3 B(n)=k=1mknk!j=0m-k(-1)jj!,
mn,
26.7.4 B(n)=-1k=1knk!=1+-1k=12nknk!.

See Table 26.7.1.

Table 26.7.1: Bell numbers.
n B(n) n B(n)
0 1 10 1 15975
1 1 11 6 78570
2 2 12 42 13597
3 5 13 276 44437
4 15 14 1908 99322
5 52 15 13829 58545
6 203 16 1 04801 42147
7 877 17 8 28648 69804
8 4140 18 68 20768 06159
9 21147 19 583 27422 05057

§26.7(ii) Generating Function

§26.7(iii) Recurrence Relation

26.7.6 B(n+1)=k=0n(nk)B(k).

§26.7(iv) Asymptotic Approximation

26.7.7 B(n)=NnN-n-1(1+lnN)1/2(1+O((lnn)1/2n1/2)),
n,

where

26.7.8 NlnN=n,

or, equivalently, N=Wm(n), with properties of the Lambert function Wm(n) given in §4.13. For higher approximations to B(n) as n see de Bruijn (1961, pp. 104–108).