§26.7 Set Partitions: Bell Numbers

§26.7(i) Definitions

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

 26.7.1 $B\left(0\right)=1,$ ⓘ Symbols: $B\left(\NVar{n}\right)$: Bell number Permalink: http://dlmf.nist.gov/26.7.E1 Encodings: TeX, pMML, png See also: Annotations for §26.7(i), §26.7 and Ch.26
 26.7.2 $B\left(n\right)=\sum_{k=0}^{n}S\left(n,k\right),$
 26.7.3 $B\left(n\right)=\sum_{k=1}^{m}\frac{k^{n}}{k!}\sum_{j=0}^{m-k}\frac{(-1)^{j}}{% j!},$ $m\geq n$,
 26.7.4 $B\left(n\right)={\mathrm{e}}^{-1}\sum_{k=1}^{\infty}\frac{k^{n}}{k!}=1+\left% \lfloor{\mathrm{e}}^{-1}\sum_{k=1}^{2n}\frac{k^{n}}{k!}\right\rfloor.$

See Table 26.7.1.

§26.7(ii) Generating Function

 26.7.5 $\sum_{n=0}^{\infty}B\left(n\right)\frac{x^{n}}{n!}=\exp({\mathrm{e}}^{x}-1).$

§26.7(iii) Recurrence Relation

26.7.6 $B\left(n+1\right)=\sum_{k=0}^{n}\genfrac{(}{)}{0.0pt}{}{n}{k}B\left(k\right).$

§26.7(iv) Asymptotic Approximation

 26.7.7 $B\left(n\right)=\frac{N^{n}{\mathrm{e}}^{N-n-1}}{(1+\ln N)^{1/2}}\left(1+O% \left(\frac{(\ln n)^{1/2}}{n^{1/2}}\right)\right),$ $n\to\infty$,

where

 26.7.8 $N\ln N=n,$ ⓘ Symbols: $\ln\NVar{z}$: principal branch of logarithm function, $n$: nonnegative integer and $N$ Permalink: http://dlmf.nist.gov/26.7.E8 Encodings: TeX, pMML, png See also: Annotations for §26.7(iv), §26.7 and Ch.26

or, specifically, $N={\mathrm{e}}^{\operatorname{Wp}\left(n\right)}$, with properties of the Lambert function $\operatorname{Wp}\left(n\right)$ given in §4.13. For higher approximations to $B\left(n\right)$ as $n\to\infty$ see de Bruijn (1961, pp. 104–108).