🌐 US-Proxy
id="topics">
TOPICS
Search

Bell Number

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The Bell number B_n, for a nonnegative integer n, counts the ways a set of n elements can be partitioned into nonempty subsets (not to be confused with the Bernoulli number, which is also commonly denoted B_n).

Equivalently, in the terminology of the twelvefold way, B_n is the number of ways of distributing n distinct balls into an unrestricted number of nonempty identical boxes.

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, ... (OEIS A000110). The numbers of digits in B_(10^n) for n=0, 1, ... are given by 1, 6, 116, 1928, 27665, ... (OEIS A113015).

Bell numbers are implemented in the Wolfram Language as BellB[n].

Though Bell numbers have traditionally been attributed to E. T. Bell as a result of the general theory he developed in his 1934 paper (Bell 1934), the first systematic study of Bell numbers was made by Ramanujan in chapter 3 of his second notebook approximately 25-30 years prior to Bell's work (B. C. Berndt, pers. comm., Jan. 4 and 13, 2010).

The first few prime Bell numbers occur at indices n=2, 3, 7, 13, 42, 55, 2841, ... (OEIS A051130), with no others less than 30447 (Weisstein, Apr. 23, 2006). These correspond to the numbers 2, 5, 877, 27644437, ... (OEIS A051131). B_(2841) was proved prime by I. Larrosa Canestro in 2004 after 17 months of computation using the elliptic curve primality proving program PRIMO.

BellNumbers

Bell numbers are closely related to Catalan numbers. The diagram above 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=0)^nS(n,k),
(1)

where S(n,k) is a Stirling number of the second kind, i.e., as the Stirling transform of the sequence 1, 1, 1, ....

For n>=1, the Bell numbers are given in terms of generalized hypergeometric functions by

B_n=e^(-1)_(n-1)F_(n-1)(2,...,2_()_(n-1);1,...,1_()_(n-1);1)
(2)

(K. A. Penson, pers. comm., Jan. 14, 2007).

The Bell numbers can also be generated using the sum and recurrence relation

B_n=sum_(k=0)^(n-1)B_k(n-1; k),
(3)

where (a; b) is a binomial coefficient, using the formula of Comtet (1974)

B_n=[e^(-1)sum_(m=1)^(2n)(m^n)/(m!)]
(4)

for n>0, where [x] denotes the ceiling function. Dobiński's formula gives the nth Bell number for n>=1,

B_n=1/esum_(k=0)^infty(k^n)/(k!).
(5)

For n>=1, a variation of Dobiński's formula gives

B_n=sum_(k=1)^(n)(k^n)/(k!)sum_(j=0)^(n-k)((-1)^j)/(j!)
(6)
=sum_(m=1)^(n)(m^n!(n-m))/(Gamma(m+1)Gamma(n-m+1)),
(7)

where !n is a subfactorial (Pitman 1997).

For n>=1, a double sum is given by

B_n=sum_(k=1)^nsum_(i=1)^k((-1)^(k-i)(k; i)i^n)/(k!).
(8)

The ordinary generating function sum_(n=0)^(infty)B_nx^n is a formal power series with radius of convergence zero. For x<0, the function

G(x)=1/esum_(k=0)^(infty)1/((1-kx)k!)
(9)
=sum_(k=0)^(infty)(x^k)/((-x)^k((x-1)/x)_k)
(10)
=(_1F_1(-1/x;(x-1)/x;1))/e
(11)
=((-1)^(1/x)[xGamma(1-x^(-1))+Gamma(-x^(-1),-1)])/(ex)
(12)
∼1+x+2x^2+5x^3+15x^4+52x^5+...,
(13)

has the Bell numbers as its asymptotic coefficients as x->0^-. The exponential generating function is

e^(e^x-1)=sum_(n=0)^infty(B_n)/(n!)x^n.
(14)

An amazing integral representation for B_n was given by Cesàro (1885),

B_n=(2n!)/(pie)Im[int_0^pie^(e^(e^(itheta)))sin(ntheta)dtheta]
(15)
=(2n!)/(pie)int_0^pie^(e^(costheta)cos(sintheta))sin[e^(costheta)sin(sintheta)]sin(ntheta)dtheta
(16)

(Becker and Browne 1941, Callan 2005) for n>=1, where Im[z] denotes the imaginary part of z.

The Bell number B_n is also equal to phi_n(1), where phi_n(x) is a Bell polynomial.

de Bruijn (1981) gave the asymptotic formula

(lnB_n)/n=lnn-lnlnn-1+(lnlnn)/(lnn)+1/(lnn)+1/2((lnlnn)/(lnn))^2+O[(lnlnn)/((lnn)^2)].
(17)

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

B_n∼n^(-1/2)[lambda(n)]^(n+1/2)e^(lambda(n)-n-1),
(18)

where lambda(n)=n/W(n) and W(n) is the Lambert W-function (Graham et al. 1994, p. 493). Odlyzko (1995) gave

B_n∼(n!)/(sqrt(2piW^2(n)e^(W(n))))(e^(e^(W(n))-1))/(W^n(n)).
(19)

Touchard's congruence states

B_(p+k)=B_k+B_(k+1) (mod p)
(20)

when p is prime and k is a nonnegative integer. This gives as a special case for k=0 the congruence

B_p=2 (mod p)
(21)

for p prime. For every prime number p, the congruence

B_(n+(p^p-1)/(p-1))=B_n (mod p)
(22)

holds for all nonnegative integers n (Lunnon et al. 1979, Montgomery et al. 2010). It is conjectured that (p^p-1)/(p-1) is always the least period modulo p. The sequence of Bell numbers {B_1,B_2,...} is periodic modulo every positive integer m (Levine and Dalton 1962, Lunnon et al. 1979). The least periods for moduli m=1, 2, ... are 1, 3, 13, 12, 781, 39, 137257, 24, 39, 2343, 28531167061, 156, ... (OEIS A054767).

The Bell numbers also have the curious property that

|B_0 B_1 B_2 ... B_n; B_1 B_2 B_3 ... B_(n+1); | | | ... |; B_n B_(n+1) B_(n+2) ... B_(2n)|=product_(i=1)^(n)i!
(23)
=G(n+2)
(24)

(Lenard 1992; Radoux 1992, p. 6; Ehrenborg 2000, pp. 557-558), where the product is simply a superfactorial and G(n) is a Barnes G-function, the first few of which for n=0, 1, 2, ... are 1, 1, 2, 12, 288, 34560, 24883200, ... (OEIS A000178).

See also

Bell Polynomial, Bell Triangle, Complementary Bell Number, Complete Bell Polynomial, Dobiński's Formula, Integer Sequence Primes, Ordered Bell Number, Stirling Number of the Second Kind, Touchard's Congruence, Twelvefold Way

Explore with Wolfram|Alpha

References

Becker, H. W. and Browne, D. E. "Problem E461 and Solution." Amer. Math. Monthly 48, 701-703, 1941.Bell, E. T. "Exponential Numbers." Amer. Math. Monthly 41, 411-419, 1934.Blasiak, P.; Penson, K. A.; and Solomon, A. I. "Dobiński-Type Relations and the Log-Normal Distribution." J. Phys. A: Math. Gen. 36, L273-278, 2003.Callan, D. "Cesàro's Integral Formula for the Bell Numbers (Corrected)." Oct. 3, 2005. https://pages.stat.wisc.edu/~callan/papersother/cesaro/cesaro.pdf.Cesàro, M. E. "Sur une équation aux différences mêlées." Nouv. Ann. Math. 4, 36-40, 1885.Comtet, L. Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. 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, 1981.Dickau, R. "Visualizing Combinatorial Enumeration." Mathematica in Educ. Res. 8, 11-18, 1999.Dickau, R. M. "Bell Number Diagrams." https://www.robertdickau.com/bell.html.Ehrenborg, R. "The Hankel Determinant of Exponential Polynomials." Amer. Math. Monthly 107, 557-560, 2000. https://doi.org/10.1080/00029890.2000.12005236.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, pp. 24-38, 1992.Gould, H. W. Bell & Catalan Numbers: Research Bibliography of Two Special Number Sequences, 6th ed. Morgantown, WV: Math Monongliae, 1985.Graham, R. L.; Knuth, D. E.; and Patashnik, O. Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, 1994.Update a linkLarrosa Canestro, I. "Bell(2841) Is Prime." Feb. 13, 2004. http://groups.yahoo.com/group/primenumbers/message/14558Lenard, 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 Integers." Math. Comput. 16, 416-423, 1962. https://doi.org/10.1090/S0025-5718-1962-0148604-2.Lovász, L. Combinatorial Problems and Exercises, 2nd ed. Amsterdam, Netherlands: North-Holland, 1993.Lunnon, W. F.; Pleasants, P. A. B.; and Stephens, N. M. "Arithmetic Properties of Bell Numbers to a Composite Modulus, I." Acta Arith. 35, 1-16, 1979. https://doi.org/10.4064/aa-35-1-1-16.Montgomery, P. L.; Nahm, S.; and Wagstaff, S. S., Jr. "The Period of the Bell Numbers Modulo a Prime." Math. Comput. 79, 1793-1800, 2010. https://doi.org/10.1090/S0025-5718-10-02340-9.Odlyzko, A. M. "Asymptotic Enumeration Methods." In Handbook of Combinatorics, Vol. 2 (Ed. R. L. Graham, M. Grötschel, and L. Lovász). Cambridge, MA: MIT Press, pp. 1063-1229, 1995. https://www.dtc.umn.edu/~odlyzko/doc/asymptotic.enum.pdf.Penson, K. A.; Blasiak, P.; Duchamp, G.; Horzela, A.; and Solomon, A. I. "Hierarchical Dobiński-Type Relations via Substitution and the Moment Problem." 26 Dec 2003. https://arxiv.org/abs/quant-ph/0312202.Pitman, J. "Some Probabilistic Aspects of Set Partitions." Amer. Math. Monthly 104, 201-209, 1997.Radoux, C. "Déterminants de Hankel et théorème de Sylvester." Sém. Lothar. Combin. 28, B28b, 1992. https://www.mat.univie.ac.at/~slc/opapers/s28radoux.html.Rota, G.-C. "The Number of Partitions of a Set." Amer. Math. Monthly 71, 498-504, 1964.Sixdeniers, J.-M.; Penson, K. A.; and Solomon, A. I. "Extended Bell and Stirling Numbers from Hypergeometric Functions." J. Integer Sequences 4, No. 01.1.4, 2001. https://cs.uwaterloo.ca/journals/JIS/VOL4/SIXDENIERS/bell.html.Sloane, N. J. A. Sequences A000110/M1484, A000178/M2049, A051130, A051131, A054767, and A113015 in "The On-Line Encyclopedia of Integer Sequences."Stanley, R. P. Enumerative Combinatorics, Vol. 1. Cambridge, England: Cambridge University Press, pp. 33-34, 1999.Stanley, R. P. Enumerative Combinatorics, Vol. 2. Cambridge, England: Cambridge University Press, p. 13, 1999.Wilson, D. "Bell Number Question." math-fun@cs.arizona.edu mailing list. 16 Jul 2007.

Referenced on Wolfram|Alpha

Bell Number

Cite this as:

Weisstein, Eric W. "Bell Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BellNumber.html

Subject classifications