Bell Number

The number of ways a Set of $n$ elements can be Partitioned into nonempty Subsets is called a Bell Number and is denoted $B_n$. For example, there are five ways the numbers $\{$1, 2, 3$\}$ can be partitioned: $\{\{1\}, \{2\}, \{3\}\}$, $\{\{1, 2\}, \{3\}\}$, $\{\{1, 3\}, \{2\}\}$, $\{\{1\}, \{2, 3\}\}$, and $\{\{1, 2, 3\}\}$, so $B_3=5$. $B_0=1$ and the first few Bell numbers for $n=1$, 2, ... are 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, ... (Sloane's A000110). Bell numbers are closely related to Catalan Numbers.

The diagram below shows the constructions giving $B_3=5$ and $B_4=15$, with line segments representing elements in the same Subset and dots representing subsets containing a single element (Dickau).

The Integers $B_n$ can be defined by the sum

$$B_n=\sum_{k=1}^n \left\{\matrix{n\cr k}\right\},$$ (1)

where $S_n^{(k)}=\left\{\matrix{n\cr k}\right\}$ is a Stirling Number of the Second Kind, or by the generating function

$$e^{e^x-1} =\sum_{n=0}^\infty {B_n\over n!} x^n.$$ (2)

The Bell numbers can also be generated using the Bell Triangle, using the Recurrence Relation

$$B_{n+1}=\sum_{k=0}^n B_k{n\choose k},$$ (3)

where ${a\choose b}$ is a Binomial Coefficient, or using the formula of Comtet (1974)

$$B_n=\left\lceil{e^{-1}\sum_{m=1}^{2n} {m^n\over m!}}\right\rceil ,$$ (4)

where $\left\lceil{x}\right\rceil$ denotes the Ceiling Function.

The Bell number $B_n$ is also equal to $\phi_n(1)$, where $\phi_n(x)$ is a Bell Polynomial. Dobinski's Formula gives the $n$th Bell number

$$B_n={1\over e}\sum_{k=0}^\infty {k^n\over k!}.$$ (5)

Lovász (1993) showed that this formula gives the asymptotic limit

$$B_n\sim n^{-1/2} [\lambda(n)]^{n+1/2}e^{\lambda(n)-n-1},$$ (6)

where $\lambda(n)$ is defined implicitly by the equation

$$\lambda(n)\log[\lambda(n)]=n.$$ (7)

A variation of Dobinski's Formula gives

$$B_n=\sum_{k=1}^n {k^n\over k!}\sum_{j=0}^{n-k} {(-1)^j\over j!}$$ (8)

(Pitman 1997). de Bruijn (1958) gave the asymptotic formula

$${\ln B_n\over n}=\ln n-\ln\ln n-1+{\ln\ln n\over\ln n}+{1\ov... ...n}\right)^2+{\mathcal O}\left[{\ln\ln n\over(\ln n)^2}\right].$$ (9)

Touchard's Congruence states

$$B_{p+k}\equiv B_k+B_{k+1}\ \left({{\rm mod\ } {p}}\right),$$ (10)

when $p$ is Prime. The only Prime Bell numbers for $n\leq 1000$ are $B_2$, $B_3$, $B_7$, $B_{13}$, $B_{42}$, and $B_{55}$. The Bell numbers also have the curious property that

$$\left\vert\matrix{ B_0 & B_1 & B_2 & \cdots & B_n\cr B_1 & B... ... & B_{n+2} & \cdots & B_{2n}\cr}\right\vert = \prod_{i=1}^n n!$$ (11)

(Lenard 1986).

See also Bell Polynomial, Bell Triangle, Dobinski's Formula, Stirling Number of the Second Kind, Touchard's Congruence

References

Bell, E. T. ``Exponential Numbers.'' Amer. Math. Monthly 41, 411-419, 1934.

Comtet, L. Advanced Combinatorics. Dordrecht, Netherlands: Reidel, 1974.

Conway, J. H. and Guy, R. K. In The Book of Numbers. New York: Springer-Verlag, pp. 91-94, 1996.

de Bruijn, N. G. Asymptotic Methods in Analysis. New York: Dover, pp. 102-109, 1958.

Dickau, R. M. ``Bell Number Diagrams.'' http://forum.swarthmore.edu/advanced/robertd/bell.html.

Gardner, M. ``The Tinkly Temple Bells.'' Ch. 2 in Fractal Music, Hypercards, and More Mathematical Recreations from Scientific American Magazine. New York: W. H. Freeman, 1992.

Gould, H. W. Bell & Catalan Numbers: Research Bibliography of Two Special Number Sequences, 6th ed. Morgantown, WV: Math Monongliae, 1985.

Lenard, A. In Fractal Music, Hypercards, and More Mathematical Recreations from Scientific American Magazine. (M. Gardner). New York: W. H. Freeman, pp. 35-36, 1992.

Levine, J. and Dalton, R. E. ``Minimum Periods, Modulo $p$, of First Order Bell Exponential Integrals.'' Math. Comput. 16, 416-423, 1962.

Lovász, L. Combinatorial Problems and Exercises, 2nd ed. Amsterdam, Netherlands: North-Holland, 1993.

Pitman, J. ``Some Probabilistic Aspects of Set Partitions.'' Amer. Math. Monthly 104, 201-209, 1997.

Rota, G.-C. ``The Number of Partitions of a Set.'' Amer. Math. Monthly 71, 498-504, 1964.

Sloane, N. J. A. Sequence A000110/M1484 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.