§26.7 Set Partitions: Bell Numbers

Permalink:: http://dlmf.nist.gov/26.7

§26.7(i) Definitions
§26.7(ii) Generating Function
§26.7(iii) Recurrence Relation
§26.7(iv) Asymptotic Approximation

§26.7(i) Definitions

Notes:: See Comtet (1974, pp. 210–211). (26.7.3) is from Wilf (1994, p. 22). Table 26.7.1 was computed by the author.
Defines:: $\mathop{B\/}\nolimits\!\left(n\right)$ : Bell number
Keywords:: Bell numbers
Permalink:: http://dlmf.nist.gov/26.7.i

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

26.7.1 $\mathop{B\/}\nolimits\!\left(0\right)=1,$

Symbols:: $\mathop{B\/}\nolimits\!\left(n\right)$ : Bell number
Permalink:: http://dlmf.nist.gov/26.7.E1
Encodings:: TeX, pMML, png

26.7.2 $\mathop{B\/}\nolimits\!\left(n\right)=\sum _{{k=0}}^{n}\mathop{S\/}\nolimits\!\left(n,k\right),$

Symbols:: $\mathop{B\/}\nolimits\!\left(n\right)$ : Bell number, $\mathop{S\/}\nolimits\!\left(n,k\right)$ : Stirling number of the second kind, $k$ : nonnegative integer and $n$ : nonnegative integer
Permalink:: http://dlmf.nist.gov/26.7.E2
Encodings:: TeX, pMML, png

26.7.3 $\mathop{B\/}\nolimits\!\left(n\right)=\sum _{{k=1}}^{{m}}\frac{k^{n}}{k!}\sum _{{j=0}}^{{m-k}}\frac{(-1)^{j}}{j!},$ $m\geq n$ ,

Symbols:: $\mathop{B\/}\nolimits\!\left(n\right)$ : Bell number, $!$ : $n!$ : factorial, $j$ : nonnegative integer, $k$ : nonnegative integer, $m$ : nonnegative integer and $n$ : nonnegative integer
Referenced by:: §26.7(i)
Permalink:: http://dlmf.nist.gov/26.7.E3
Encodings:: TeX, pMML, png

26.7.4 $\mathop{B\/}\nolimits\!\left(n\right)=e^{{-1}}\sum _{{k=1}}^{{\infty}}\frac{k^{n}}{k!}=1+\left\lfloor e^{{-1}}\sum _{{k=1}}^{{2n}}\frac{k^{n}}{k!}\right\rfloor.$

Symbols:: $\mathop{B\/}\nolimits\!\left(n\right)$ : Bell number, $e$ : base of exponential function, $!$ : $n!$ : factorial, $\left\lfloor x\right\rfloor$ : floor of $x$ , $k$ : nonnegative integer and $n$ : nonnegative integer
Permalink:: http://dlmf.nist.gov/26.7.E4
Encodings:: TeX, pMML, png

See Table 26.7.1.

Table 26.7.1: Bell numbers.

$n$	$\mathop{B\/}\nolimits\!\left(n\right)$	$n$	$\mathop{B\/}\nolimits\!\left(n\right)$
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

Symbols:: $\mathop{B\/}\nolimits\!\left(n\right)$ : Bell number and $n$ : nonnegative integer
Keywords:: Bell numbers
Referenced by:: §26.7(i), §26.7(i)
Permalink:: http://dlmf.nist.gov/26.7.T1

§26.7(ii) Generating Function

Notes:: See Comtet (1974, p.210).
Keywords:: Bell numbers
Permalink:: http://dlmf.nist.gov/26.7.ii

26.7.5 $\sum _{{n=0}}^{{\infty}}\mathop{B\/}\nolimits\!\left(n\right)\frac{x^{n}}{n!}=\mathop{\exp\/}\nolimits(e^{x}-1).$

Symbols:: $\mathop{B\/}\nolimits\!\left(n\right)$ : Bell number, $\mathop{\exp\/}\nolimits z$ : exponential function, $e$ : base of exponential function, $!$ : $n!$ : factorial, $x$ : real variable and $n$ : nonnegative integer
Permalink:: http://dlmf.nist.gov/26.7.E5
Encodings:: TeX, pMML, png

§26.7(iii) Recurrence Relation

Notes:: See Comtet (1974, p.210).
Keywords:: Bell numbers
Permalink:: http://dlmf.nist.gov/26.7.iii

26.7.6 $\mathop{B\/}\nolimits\!\left(n+1\right)=\sum _{{k=0}}^{n}\binom{n}{k}\mathop{B\/}\nolimits\!\left(k\right).$

Symbols:: $\mathop{B\/}\nolimits\!\left(n\right)$ : Bell number, $\binom{m}{n}$ : binomial coefficient, $k$ : nonnegative integer and $n$ : nonnegative integer
Referenced by:: Version 1.0.1 (June 27, 2011)
Permalink:: http://dlmf.nist.gov/26.7.E6
Encodings:: TeX, pMML, png
Errata (effective with 1.0.1):: Originally appeared with $\mathop{B\/}\nolimits\!\left(n\right)$ in the summation, instead of $\mathop{B\/}\nolimits\!\left(k\right)$ :
$\mathop{B\/}\nolimits\!\left(n+1\right)=\sum _{{k=0}}^{n}\binom{n}{k}\mathop{B\/}\nolimits\!\left(n\right)$

Reported 2010-11-07 by Layne Watson

§26.7(iv) Asymptotic Approximation

Notes:: See de Bruijn (1961, pp. 104–108) and Olver (1997b, pp. 329–331).
Keywords:: Bell numbers
Permalink:: http://dlmf.nist.gov/26.7.iv

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

Symbols:: $\mathop{B\/}\nolimits\!\left(n\right)$ : Bell number, $\mathop{O\/}\nolimits\!\left(x\right)$ : order not exceeding, $e$ : base of exponential function, $\mathop{\ln\/}\nolimits z$ : principal branch of logarithm function, $n$ : nonnegative integer and $N$
Permalink:: http://dlmf.nist.gov/26.7.E7
Encodings:: TeX, pMML, png

where

26.7.8 $N\mathop{\ln\/}\nolimits N=n,$

Symbols:: $\mathop{\ln\/}\nolimits z$ : principal branch of logarithm function, $n$ : nonnegative integer and $N$
Permalink:: http://dlmf.nist.gov/26.7.E8
Encodings:: TeX, pMML, png

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

§26.7 Set Partitions: Bell Numbers

Contents

§26.7(i) Definitions

§26.7(ii) Generating Function

§26.7(iii) Recurrence Relation

§26.7(iv) Asymptotic Approximation