About the Project
26 Combinatorial AnalysisProperties

§26.7 Set Partitions: Bell Numbers

Contents
  1. §26.7(i) Definitions
  2. §26.7(ii) Generating Function
  3. §26.7(iii) Recurrence Relation
  4. §26.7(iv) Asymptotic Approximation

§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.2 B(n)=k=0nS(n,k),
26.7.3 B(n)=k=1mknk!j=0mk(1)jj!,
mn,
26.7.4 B(n)=e1k=1knk!=1+e1k=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.5 n=0B(n)xnn!=exp(ex1).

§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)=NneNn1(1+lnN)1/2(1+O((lnn)1/2n1/2)),
n,

where

26.7.8 NlnN=n,

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