26 Combinatorial Analysis Properties 26.6 Other Lattice Path Numbers 26.8 Set Partitions: Stirling Numbers

§26.7 Set Partitions: Bell Numbers

ⓘ

Permalink:: http://dlmf.nist.gov/26.7
See also:: Annotations for Ch.26

§26.7(i) Definitions

ⓘ

Defines:: $B\left(\NVar{n}\right)$ : Bell number
Keywords:: Bell numbers, definition
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.
Permalink:: http://dlmf.nist.gov/26.7.i
See also:: Annotations for §26.7 and Ch.26

$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),$
ⓘ Symbols: $B\left(\NVar{n}\right)$ : Bell number, $S\left(\NVar{n},\NVar{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 See also: Annotations for §26.7(i), §26.7 and Ch.26

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$ ,
ⓘ Symbols: $B\left(\NVar{n}\right)$ : Bell number, $!$ : factorial (as in $n!$ ), $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 See also: Annotations for §26.7(i), §26.7 and Ch.26

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.$
ⓘ Symbols: $B\left(\NVar{n}\right)$ : Bell number, $\mathrm{e}$ : base of natural logarithm, $!$ : factorial (as in $n!$ ), $\left\lfloor\NVar{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 also: Annotations for §26.7(i), §26.7 and Ch.26

See Table 26.7.1.

Table 26.7.1: Bell numbers.

$n$	$B\left(n\right)$	$n$	$B\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:: $B\left(\NVar{n}\right)$ : Bell number and $n$ : nonnegative integer
Keywords:: Bell numbers, table
Referenced by:: §26.7(i), §26.7(i)
Permalink:: http://dlmf.nist.gov/26.7.T1
See also:: Annotations for §26.7(i), §26.7 and Ch.26

§26.7(ii) Generating Function

ⓘ

Keywords:: Bell numbers, generating function
Notes:: See Comtet (1974, p.210).
Permalink:: http://dlmf.nist.gov/26.7.ii
See also:: Annotations for §26.7 and Ch.26

26.7.5		$\sum_{n=0}^{\infty}B\left(n\right)\frac{x^{n}}{n!}=\exp({\mathrm{e}}^{x}-1).$
ⓘ Symbols: $B\left(\NVar{n}\right)$ : Bell number, $\exp\NVar{z}$ : exponential function, $\mathrm{e}$ : base of natural logarithm, $!$ : factorial (as in $n!$ ), $x$ : real variable and $n$ : nonnegative integer Permalink: http://dlmf.nist.gov/26.7.E5 Encodings: TeX, pMML, png See also: Annotations for §26.7(ii), §26.7 and Ch.26

§26.7(iii) Recurrence Relation

ⓘ

Keywords:: Bell numbers, recurrence relation
Notes:: See Comtet (1974, p.210).
Permalink:: http://dlmf.nist.gov/26.7.iii
See also:: Annotations for §26.7 and Ch.26

26.7.6

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

ⓘ

Symbols:

B\left(\NVar{n}\right)

: Bell number,

\genfrac{(}{)}{0.0pt}{}{\NVar{m}}{\NVar{n}}

: binomial coefficient,

k

: nonnegative integer and

n

: nonnegative integer

Referenced by:

Erratum (V1.0.1) for Equation (26.7.6)

Permalink:

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

Encodings:

TeX, pMML, png

Errata (effective with 1.0.1):

Originally appeared with

B\left(n\right)

in the summation, instead of

B\left(k\right)

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

Reported 2010-11-07 by Layne Watson

See also:

Annotations for §26.7(iii), §26.7 and Ch.26

§26.7(iv) Asymptotic Approximation

ⓘ

Keywords:: Bell numbers, asymptotic approximations
Notes:: See de Bruijn (1961, pp. 104–108) and Olver (1997b, pp. 329–331).
Referenced by:: Erratum (V1.0.21) for Subsection 26.7(iv), Erratum (V1.2.2) for Subsection 26.7(iv)
Permalink:: http://dlmf.nist.gov/26.7.iv
Modification (effective with 1.2.2):: Immediately below (26.7.8), $\operatorname{Wp}\left(n\right)$ was replaced with $W_{0}\left(n\right)$ twice and the text “Lambert function” was replaced with the text “Lambert $W$ -function”.
Correction (effective with 1.0.21):: In the final line of this subsection, $\operatorname{Wm}\left(n\right)$ was replaced by $\operatorname{Wp}\left(n\right)$ twice. Also, the wording “or, equivalently, $N={\mathrm{e}}^{\operatorname{Wm}\left(n\right)}$ ” was changed to “or, specifically, $N={\mathrm{e}}^{\operatorname{Wp}\left(n\right)}$ ”.
Suggested 2018-04-09 by Gergő Nemes
See also:: Annotations for §26.7 and Ch.26

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$ ,
ⓘ Symbols: $B\left(\NVar{n}\right)$ : Bell number, $O\left(\NVar{x}\right)$ : order not exceeding, $\mathrm{e}$ : base of natural logarithm, $\ln\NVar{z}$ : principal branch of logarithm function, $n$ : nonnegative integer and $N$ Permalink: http://dlmf.nist.gov/26.7.E7 Encodings: TeX, pMML, png See also: Annotations for §26.7(iv), §26.7 and Ch.26

where

26.7.8		$N\ln N=n,$
ⓘ Symbols: $\ln\NVar{z}$ : principal branch of logarithm function, $n$ : nonnegative integer and $N$ Referenced by: §26.7(iv), Erratum (V1.2.2) for Subsection 26.7(iv) 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}}^{W_{0}\left(n\right)}$ , with properties of the Lambert $W$ -function $W_{0}\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).

26.6 Other Lattice Path Numbers 26.8 Set Partitions: Stirling Numbers

NIST

Site Privacy Accessibility Privacy Program Copyrights Vulnerability Disclosure No Fear Act Policy FOIA Environmental Policy Scientific Integrity Information Quality Standards Commerce.gov Science.gov USA.gov

§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