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
§26.7(ii) Generating Function
§26.7(iii) Recurrence Relation
§26.7(iv) Asymptotic Approximation

§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, : nonnegative integer and : 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 ), : nonnegative integer, : nonnegative integer, : nonnegative integer and : 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 ), $\left\lfloor\NVar{x}\right\rfloor$ : floor of , : nonnegative integer and : 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.

	$B\left(n\right)$		$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 : 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 ), : real variable and : 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, : nonnegative integer and : 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 -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, : nonnegative integer and
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, : nonnegative integer and
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 -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

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