World Library  
Flag as Inappropriate
Email this Article

Bell number

Article Id: WHEBN0000201022
Reproduction Date:

Title: Bell number  
Author: World Heritage Encyclopedia
Language: English
Subject: Catalan number, Eric Temple Bell, Kynea number, Carol number, Proth number
Collection: Integer Sequences
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Bell number

In combinatorial mathematics, the Bell numbers count the number of partitions of a set. These numbers have been studied by mathematicians since the 19th century, and their roots go back to medieval Japan, but they are named after Eric Temple Bell, who wrote about them in the 1930s.

Starting with B0 = B1 = 1, the first few Bell numbers are:

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057, ... (sequence A000110 in OEIS).

The nth of these numbers, Bn, counts the number of different ways to partition a set that has exactly n elements, or equivalently, the number of equivalence relations on it. Outside of mathematics, the same number also counts the number of different rhyme schemes for n-line poems.[1]

As well as appearing in counting problems, these numbers have a different interpretation, as moments of probability distributions. In particular, Bn is the nth moment of a Poisson distribution with mean 1.

Contents

  • What these numbers count 1
    • Set partitions 1.1
    • Factorizations 1.2
    • Rhyme schemes 1.3
    • Permutations 1.4
  • Triangle scheme for calculations 2
  • Properties 3
    • Summation formulas 3.1
    • Generating function 3.2
    • Moments of probability distributions 3.3
    • Modular arithmetic 3.4
    • Integral representation 3.5
    • Log-concavity 3.6
  • Growth rate 4
  • Bell primes 5
  • History 6
  • See also 7
  • Notes 8
  • References 9
  • External links 10

What these numbers count

Set partitions

Partitions of sets can be arranged in a partial order, showing that each partition of a set of size n "uses" one of the partitions of a set of size n-1.
The 52 partitions of a set with 5 elements

In general, Bn is the number of partitions of a set of size n. A partition of a set S is defined as a set of nonempty, pairwise disjoint subsets of S whose union is S. For example, B3 = 5 because the 3-element set {abc} can be partitioned in 5 distinct ways:

{ {a}, {b}, {c} }
{ {a}, {b, c} }
{ {b}, {a, c} }
{ {c}, {a, b} }
{ {a, b, c} }.

B0 is 1 because there is exactly one partition of the empty set. Every member of the empty set is a nonempty set (that is vacuously true), and their union is the empty set. Therefore, the empty set is the only partition of itself. As suggested by the set notation above, we consider neither the order of the partitions nor the order of elements within each partition. This means that the following partitionings are all considered identical:

{ {b}, {a, c} }
{ {a, c}, {b} }
{ {b}, {c, a} }
{ {c, a}, {b} }.

If, instead, different orderings of the sets are considered to be different partitions, then the number of these ordered partitions is given by the ordered Bell numbers.

Factorizations

If a number N is a squarefree number (meaning that it is the product of some number n of distinct prime numbers), then Bn gives the number of different multiplicative partitions of N. These are factorizations of N into numbers greater than one, treating two factorizations as the same if they have the same factors in a different order.[2] For instance, 30 is the product of the three primes 2, 3, and 5, and has five factorizations:

30\times 1=2\times 15=3\times 10=5\times 6=2\times 3\times 5

Rhyme schemes

The Bell numbers also count the rhyme schemes of an n-line poem or stanza. A rhyme scheme describes which lines rhyme with each other, and so may be interpreted as a partition of the set of lines into rhyming subsets. Rhyme schemes are usually written as sequence of Roman letters, one per line, with rhyming lines given the same letter as each other, and with the first lines in each rhyming set labeled in alphabetical order. Thus, the 15 possible four-line rhyme schemes are AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC, and ABCD.[1]

Permutations

The Bell numbers come up in a card shuffling problem mentioned in the addendum to Gardner (1978). If a deck of n cards is shuffled by repeatedly removing the top card and reinserting it anywhere in the deck (including its original position at the top of the deck), with exactly n repetitions of this operation, then there are nn different shuffles that can be performed. Of these, the number that return the deck to its original sorted order is exactly Bn. Thus, the probability that the deck is in its original order after shuffling it in this way is Bn/nn, which is significantly larger than the 1/n! probability that would describe a uniformly random permutation of the deck.

Related to card shuffling are several other problems of counting special kinds of permutations that are also answered by the Bell numbers. For instance, the nth Bell number equals number of permutations on n items in which no three values that are in sorted order have the last two of these three consecutive. In a notation for generalized permutation patterns where values that must be consecutive are written adjacent to each other, and values that can appear non-consecutively are separated by a dash, these permutations can be described as the permutations that avoid the pattern 1-23. The permutations that avoid the generalized patterns 12-3, 32-1, 3-21, 1-32, 3-12, 21-3, and 23-1 are also counted by the Bell numbers.[3] The permutations in which every 321 pattern (without restriction on consecutive values) can be extended to a 3241 pattern are also counted by the Bell numbers.[4] However, the Bell numbers grow too quickly to count the permutations that avoid a pattern that has not been generalized in this way: by the (now proven) Stanley–Wilf conjecture, the number of such permutations is singly exponential, and the Bell numbers have a higher asymptotic growth rate than that.

Triangle scheme for calculations

The triangular array whose right-hand diagonal sequence consists of Bell numbers

The Bell numbers can easily be calculated by creating the so-called Bell triangle, also called Aitken's array or the Peirce triangle after Alexander Aitken and Charles Sanders Peirce.[5]

  1. Start with the number one. Put this on a row by itself.
  2. Start a new row with the rightmost element from the previous row as the leftmost number
  3. Determine the numbers not on the left column by taking the sum of the number to the left and the number above the number to the left (the number diagonally up and left of the number we are calculating)
  4. Repeat step three until there is a new row with one more number than the previous row
  5. The number on the left hand side of a given row is the Bell number for that row.

Here are the first five rows of the triangle constructed by these rules:

 1
 1   2
 2   3   5
 5   7  10  15
15  20  27  37  52

The Bell numbers appear on both the left and right sides of the triangle.

Properties

Summation formulas

The Bell numbers satisfy a recurrence relation involving binomial coefficients:[6]

B_{n+1}=\sum_{k=0}^{n} \binom{n}{k} B_k.

It can be explained by observing that, from an arbitrary partition of n + 1 items, removing the set containing the first item leaves a partition of a smaller set of k items for some number k that may range from 0 to n. There are \tbinom{n}{k} choices for the k items that remain after one set is removed, and Bk choices of how to partition them.

A different summation formula represents each Bell number as a sum of Stirling numbers of the second kind

B_n=\sum_{k=0}^n \left\{z^{n+1}} \, dz.

Some asymptotic representations can then be derived by a standard application of the method of steepest descent.[14]

Log-concavity

The Bell numbers form a logarithmically convex sequence. Dividing them by the factorials, Bn/n!, gives a logarithmically concave sequence.[15]

Growth rate

Several asymptotic formulas for the Bell numbers are known. In Berend & Tassa (2010) the following bounds were established:

B_n < \left( \frac{0.792 n}{\ln( n+1)} \right)^n ~;

moreover, if \varepsilon>0 then for all n > n_0(\varepsilon) ,

B_n < \left( \frac{e^{-0.6 + \varepsilon} n}{\ln(n+1)}\right)^n

where ~n_0(\varepsilon) = \max\left\{e^4,d^{-1}(\varepsilon) \right\}~ and ~d(x):= \ln \ln (x+1) - \ln \ln x + \frac{1+e^{-1}}{\ln x}\,. The Bell numbers can also be approximated using the Lambert W function, a function with the same growth rate as the logarithm, as [16]

B_n \sim \frac{1}{\sqrt{n}} \left( \frac{n}{W(n)} \right)^{n + \frac{1}{2}} \exp\left(\frac{n}{W(n)} - n - 1\right).

Moser & Wyman (1955) established the expansion

B_{n+h} = \frac{(n+h)!}{W(n)^{n+h}} \times \frac{\exp(e^{W(n)} - 1)}{(2\pi B)^{1/2}} \times \left( 1 + \frac{P_0 + hP_1 + h^2P_2}{e^{W(n)}} + \frac{Q_0 + hQ_1 + h^2Q_2 + h^3Q_3 + h^4Q_4}{e^{2W(n)}} + O(e^{-3W(n)}) \right)

uniformly for h = O(\ln(n)) as n \rightarrow \infty, where B and each P_i and Q_i are known expressions in W(n).[17]

The asymptotic expression

\begin{align} \frac{\ln B_n}{n} & = \ln n - \ln \ln n - 1 + \frac{\ln \ln n}{\ln n} + \frac{1}{\ln n} + \frac{1}{2}\left(\frac{\ln \ln n}{\ln n}\right)^2 + O\left(\frac{\ln \ln n}{(\ln n)^2} \right) \\ & {} \qquad \text{as }n\to\infty \end{align}

was established by de Bruijn (1981).

Bell primes

Gardner (1978) raised the question of whether infinitely many Bell numbers are also prime numbers. The first few Bell numbers that are prime are:

2, 5, 877, 27644437, 35742549198872617291353508656626642567, 359334085968622831041960188598043661065388726959079837 (sequence A051131 in OEIS)

corresponding to the indices 2, 3, 7, 13, 42 and 55 (sequence A051130 in OEIS).

The next Bell prime is B2841, which is approximately 9.30740105 × 106538.[18] As of 2006, it is the largest known prime Bell number. Phil Carmody showed it was a probable prime in 2002. After 17 months of computation with Marcel Martin's ECPP program Primo, Ignacio Larrosa Cañestro proved it to be prime in 2004. He ruled out any other possible primes below B6000, later extended to B30447 by Eric Weisstein.[19]

History

The Bell numbers are named after Eric Temple Bell, who wrote about them in 1938, following up a 1934 paper in which he studied the Bell polynomials.[20] Bell did not claim to have discovered these numbers; in his 1938 paper, he wrote that the Bell numbers "have been frequently investigated" and "have been rediscovered many times". Bell cites several earlier publications on these numbers, beginning with Dobiński (1877) which gives Dobinski's formula for the Bell numbers. Bell called these numbers "exponential numbers"; the name "Bell numbers" and the notation Bn for these numbers was given to them by Becker & Riordan (1948).[21]

The first exhaustive enumeration of set partitions appears to have occurred in medieval Japan, where (inspired by the popularity of the book The Tale of Genji) a parlor game called genji-ko sprang up, in which guests were given five packets of incense to smell and were asked to guess which ones were the same as each other and which were different. The 52 possible solutions, counted by the Bell number B5, were recorded by 52 different diagrams, which were printed above the chapter headings in some editions of The Tale of Genji.[22]

In Srinivasa Ramanujan's second notebook, he investigated both Bell polynomials and Bell numbers.[23] Early references for the Bell triangle, which has the Bell numbers on both of its sides, include Peirce (1880) and Aitken (1933).

See also

Notes

  1. ^ a b Gardner (1978).
  2. ^ Williams (1945) credits this observation to Silvio Minetola's Principii di Analisi Combinatoria (1909).
  3. ^ Claesson (2001).
  4. ^ Callan (2006).
  5. ^ "Sloane's A011971 : Aitken's array", The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
  6. ^ Wilf (1994), p. 23.
  7. ^ Conway & Guy (1996).
  8. ^ a b Flajolet & Sedgewick (2009).
  9. ^ Rota (1964); Wilf (1994), pp. 20–23; Bender & Williamson (2006).
  10. ^ Dobiński (1877); Rota (1964); Bender & Williamson (2006).
  11. ^ Becker & Riordan (1948).
  12. ^ Hurst & Schultz (2009).
  13. ^ Williams (1945); Wagstaff (1996).
  14. ^ Simon, Barry (2010). "Example 15.4.6 (Asymptotics of Bell Numbers)". Complex Analysis (PDF). pp. 772–774. 
  15. ^ Engel (1994); Canfield (1995); Asai, Kubo & Kuo (2000).
  16. ^ Lovász (1993).
  17. ^ Canfield, Rod (July 1994). "The Moser-Wyman expansion of the Bell numbers" (PDF). Retrieved 2013-10-24. 
  18. ^ "93074010508593618333...(6499 other digits)...83885253703080601131". 5000 Largest Known Primes, The Prime Database. Retrieved 2013-10-24. 
  19. ^ Weisstein, Eric W., "Integer Sequence Primes", MathWorld.
  20. ^ Bell (1934); Bell (1938).
  21. ^ Rota (1964). However, Rota gives an incorrect date, 1934, for Becker & Riordan (1948).
  22. ^ Knuth (2013). Gardner (1978) and Berndt (2011) also mention the connection between Bell numbers and The Tale of Genji, in less detail.
  23. ^ Berndt (2011).

References

  • Asai, Nobuhiro; Kubo, Izumi; Kuo, Hui-Hsiung (2000). "Bell numbers, log-concavity, and log-convexity". Acta Applicandae Mathematicae 63 (1-3): 79–87.  
  •  
  • Becker, H. W.;  .
  •  .
  •  .
  • Bender, Edward A.; Williamson, S. Gill (2006). "Example 11.7, Set Partitions". Foundations of Combinatorics with Applications (PDF). Dover. pp. 319–320.  
  • Berend, D.; Tassa, T. (2010). "Improved bounds on Bell numbers and on moments of sums of random variables". Probability and Mathematical Statistics 30 (2): 185–205. 
  • Berndt, Bruce C. (2011). "Ramanujan Reaches His Hand From His Grave To Snatch Your Theorems From You" (PDF). Asia Pacific Mathematics Newsletter 1 (2): 8–13. 
  •  
  • Callan, David (2006). "A combinatorial interpretation of the eigensequence for composition". Journal of Integer Sequences 9 (1): 06.1.4.  
  • Canfield, E. Rodney (1995). "Engel's inequality for Bell numbers". Journal of Combinatorial Theory. Series A 72 (1): 184–187.  
  • Claesson, Anders (2001). "Generalized pattern avoidance". European Journal of Combinatorics 22 (7): 961–971.  
  •  
  • Dobiński, G. (1877).  = 1, 2, 3, 4, 5, …"m für \textstyle\sum\frac{n^m}{n!}"Summirung der Reihe . Grunert's Archiv 61: 333–336. 
  • Engel, Konrad (1994). "On the average rank of an element in a filter of the partition lattice".  
  •  
  •   Reprinted with an addendum as "The Tinkly Temple Bells", Chapter 2 of Fractal Music, Hypercards, and more ... Mathematical Recreations from Scientific American, W. H. Freeman, 1992, pp. 24–38
  • Hazewinkel, Michiel, ed. (2001), "Bell numbers",  
  • Hurst, Greg; Schultz, Andrew (2009). "An elementary (number theory) proof of Touchard's congruence".  
  •  
  •  
  •  
  •  .
  •  
  • Spivey, Michael Z. (2008). "A generalized recurrence for Bell numbers" (PDF). Journal of Integer Sequences 11 (2): Article 08.2.5, 3.  
  •  
  •  
  • Williams, G. T. (1945). "Numbers generated by the function eex − 1".  

External links

  • Robert Dickau. "Diagrams of Bell numbers". 
  • Weisstein, Eric W., "Bell Number", MathWorld.
  • Gottfried Helms. "Further properties & Generalization of Bell-Numbers" (PDF). 
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.