[go: up one dir, main page]
Wikipedia

Bell number: Difference between revisions

Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
OAbot (talk | contribs)
Bots
435,726 edits
m Open access bot: doi added to citation with #oabot.
Undid revision 1256062525 by Aoa7386 (talk) we want to provide context to readers who do not already recognize combinatorics as the name of a mathematical subfield
 
(29 intermediate revisions by 15 users not shown)
Line 6:
 
The Bell numbers are denoted <math>B_n</math>, where <math>n</math> is an [[integer]] greater than or equal to [[zero]]. Starting with <math>B_0 = B_1 = 1</math>, the first few Bell numbers are
:<math>1, 1, 2, 5, 15, 52, 203, 877, 4140, ...\dots</math> {{OEIS|id=A000110}}.
The Bell number <math>B_n</math> counts the number of different ways to partition a set that has exactly <math>n</math> elements, or equivalently, the number of [[equivalence relation]]s on it. <math>B_n</math> also counts the number of different [[rhyme scheme]]s for <math> n </math>-line poems.{{sfn|Gardner|1978}}
 
As well as appearing in counting problems, these numbers have a different interpretation, as [[moment (mathematics)|moments]] of [[probability distribution]]s. In particular, <math>B_n</math> is the <math> n </math>-th moment of a [[Poisson distribution]] with [[mean]] 1.
Line 30:
 
===Factorizations===
If a number <math>N</math> is a [[squarefree]] positive [[integer]], meaning that it is the product of some number <math>n</math> of distinct [[prime number]]s), then <math>B_n</math> gives the number of different [[multiplicative partition]]s of <math>N</math>. These are [[factorization]]s of <math>N</math> into numbers greater than one, treating two factorizations as the same if they have the same factors in a different order.<ref>{{harvnb|Williams|1945}} credits this observation to Silvio Minetola's ''Principii di Analisi Combinatoria'' (1909).</ref> For instance, 30 is the product of the three primes 2, 3, and&nbsp;5, and has <math>B_3</math> = 5 factorizations:
:<math>30 = 2\times 15=3\times 10=5\times 6=2\times 3\times 5</math>
 
Line 37:
 
===Permutations===
The Bell numbers come up in a card [[shuffling]] problem mentioned in the addendum to {{harvtxtharvnb|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 ''n''<sup>''n''</sup> different shuffles that can be performed. Of these, the number that return the deck to its original sorted order is exactly ''B<sub>n</sub>''. Thus, the probability that the deck is in its original order after shuffling it in this way is ''B<sub>n</sub>''/''n''<sup>''n''</sup>, 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 [[permutation]]s that are also answered by the Bell numbers. For instance, the ''n''th Bell number equals the 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 pattern]]s 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.{{sfnp|Claesson|2001}} 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.{{sfnp|Callan|2006}} 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.
Line 54:
Here are the first five rows of the triangle constructed by these rules:
 
<math>
1
\begin{array}{l}
1 2
21 3 5\\
51 & 72 10 15\\
15 202 & 27 3 37& 525 \\
5 & 7 & 10 & 15 \\
15 & 20 & 27 & 37 & 52
\end{array}
</math>
 
The Bell numbers appear on both the left and right sides of the triangle.
Line 73 ⟶ 77:
The Stirling number <math>\left\{{n\atop k}\right\}</math> is the number of ways to partition a set of cardinality ''n'' into exactly ''k'' nonempty subsets. Thus, in the equation relating the Bell numbers to the Stirling numbers, each partition counted on the left hand side of the equation is counted in exactly one of the terms of the sum on the right hand side, the one for which ''k'' is the number of sets in the partition.{{sfnp|Conway|Guy|1996}}
 
{{harvtxtharvnb|Spivey|2008}} has given a formula that combines both of these summations:
:<math>B_{n+m} = \sum_{k=0}^n \sum_{j=0}^m \left\{{m\atop j}\right\} {n \choose k} j^{n-k} B_k.</math>
Applying [[Pascal's inversion formula]] to the recurrence relation, we obtain

<math display="block">B_n = \sum_{k=0}^n \binom{n}{k} (-1)^{n-k} B_{k+1},</math>
 
Whichwhich can be generalized in this manner:<ref name=":0">{{Cite journal |lastlast1=Komatsu |firstfirst1=Takao |last2=Pita-Ruiz |first2=Claudio |date=2018 |title=Some formulas for Bell numbers |url=http://www.doiserbia.nb.rs/Article.aspx?ID=0354-51801811881K |journal=Filomat |language=en |volume=32 |issue=11 |pages=3881–3889 |doi=10.2298/FIL1811881K |issn=0354-5180|doi-access=free }}</ref>▼
 
<math display="block">\sum_{j=0}^n \binom{n}{j} B_{k+j} = \sum_{i=0}^k \binom{k}{i} (-1)^{k-i} B_{n+i+1}.</math>
▲Which can be generalized in this manner<ref name=":0">{{Cite journal |last=Komatsu |first=Takao |last2=Pita-Ruiz |first2=Claudio |date=2018 |title=Some formulas for Bell numbers |url=http://www.doiserbia.nb.rs/Article.aspx?ID=0354-51801811881K |journal=Filomat |language=en |volume=32 |issue=11 |pages=3881–3889 |doi=10.2298/FIL1811881K |issn=0354-5180|doi-access=free }}</ref>
 
<math display="block">\sum_{j=0}^n \binom{n}{j} B_{k+j} = \sum_{i=0}^k \binom{k}{i} (-1)^{k-i} B_{n+i+1}</math>Other finite sum formulas using [[Stirling numbers of the first kind]] include<ref name=":0" />
 
<math display="block">\sum_{j=0}^n \binom{n}{j} a^j b^{n-j} B_j = \sum_{i=0}^k \left[{k \atop i}\right](-1)^{k-i} \sum_{j=0}^n \binom{n}{j} a^j (b-ak)^{n-j}B_{j+i},</math>
 
Whichwhich simplifies down with <math>k=1</math> to
 
<math display="block">\sum_{j=0}^n \binom{n}{j} a^j b^{n-j} B_j = \sum_{j=0}^n \binom{n}{j} a^j (b-a)^{n-j}B_{j+1}</math>
 
and with <math>a=1</math>, <math>b=k</math> to
 
<math display="block">\sum_{j=0}^n \binom{n}{j} B_j k^{n-j} = \sum_{i=0}^k \left[{k \atop i}\right] B_{n+i} (-1)^{k-i}</math>
which can be seen as the [[Stirling number#Inversion relations and the Stirling transform|inversion formula for Stirling numbers]] applied to Spivey'sSpivey’s formula.
 
===Generating function===
Line 119 ⟶ 128:
Because of Touchard's congruence, the Bell numbers are periodic modulo ''p'', for every prime number ''p''; for instance, for ''p''&nbsp;=&nbsp;2, the Bell numbers repeat the pattern odd-odd-even with period three. The period of this repetition, for an arbitrary prime number ''p'', must be a divisor of
:<math>\frac{p^p-1}{p-1}</math>
and for all prime ''<math>p'' ≤\leq 101</math> and ''<math> p'' = 113, 163, 167 </math>, or <math>173</math> it is exactly this number {{OEIS|id=A001039}}.{{sfn|Williams|1945}}{{sfn|Wagstaff|1996}}
 
The period of the Bell numbers to modulo ''n'' are
:1, 3, 13, 12, 781, 39, 137257, 24, 39, 2343, 28531167061, 156, 25239592216021, 411771, 10153, 48, 51702516367896047761, 39, 109912203092239643840221, 9372, 1784341, 85593501183, 949112181811268728834319677753, 312, 3905, 75718776648063, 117, 1647084, 91703076898614683377208150526107718802981, 30459, 568972471024107865287021434301977158534824481, 96, 370905171793, 155107549103688143283, 107197717, 156, ... {{OEIS|id=A054767}}
 
===Integral representation===
Line 134 ⟶ 143:
 
===Growth rate===
Several [[Asymptotic analysis|asymptotic]] formulas for the Bell numbers are known. In {{harvtxtharvnb|Berend|Tassa|2010}} the following bounds were established:
:<math> B_n < \left( \frac{0.792 n}{\ln( n+1)} \right)^n </math> for all positive integers <math>n</math>;
moreover, if <math> \varepsilon>0 </math> then for all <math> n > n_0(\varepsilon) </math>,
Line 144 ⟶ 153:
:<math>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). </math>
 
{{harvtxtharvnb|Moser|Wyman|1955}} established the expansion
:<math>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)</math>
uniformly for <math>h = O(\ln(n))</math> as <math>n \rightarrow \infty</math>, where <math>B</math> and each <math>P_i</math> and <math>Q_i</math> are known expressions in <math>W(n)</math>.<ref>{{cite web|url=http://www.austinmohr.com/Work_files/bellMoser.pdf|title=The Moser-Wyman expansion of the Bell numbers|first=Rod|last=Canfield|date=July 1994|access-date=2013-10-24}}</ref>
Line 157 ⟶ 166:
</math>
 
was established by {{harvtxtharvnb|de Bruijn|1981}}.
 
==Bell primes==
{{harvtxtharvnb|Gardner|1978}} raised the question of whether infinitely many Bell numbers are also [[prime number]]s. TheThese firstare fewcalled '''Bell numbersprimes'''. thatThe arefirst primefew Bell primes are:
:2, 5, 877, 27644437, 35742549198872617291353508656626642567, 359334085968622831041960188598043661065388726959079837 {{OEIS|id=A051131}}
corresponding to the indices 2, 3, 7, 13, 42 and 55 {{OEIS|id=A051130}}. The next '''Bell prime''' is ''B''<sub>2841</sub>, which is approximately 9.30740105 &times; 10<sup>6538</sup>.<ref>{{cite OEIS|A051131}}</ref>
 
The next '''Bell prime''' is ''B''<sub>2841</sub>, which is approximately 9.30740105 &times; 10<sup>6538</sup>.<ref>{{cite web|url=http://primes.utm.edu/primes/page.php?id=68825|title=93074010508593618333...83885253703080601131|work=5000 Largest Known Primes, The Prime Database|access-date=2013-10-24}}</ref> {{As of|2018}}, it is the largest known prime Bell number. [[Ignacio Larrosa Cañestro]] showed it was a [[probable prime]] in 2002. After 17 months of computation with Marcel Martin's [[Elliptic curve primality proving|ECPP]] program Primo, Ignacio Larrosa Cañestro proved it to be prime in 2004. He ruled out any other possible primes below ''B''<sub>6000</sub>, later extended to ''B''<sub>30447</sub> by [[Eric Weisstein]].<ref>{{mathworld|title=Integer Sequence Primes|id=IntegerSequencePrimes}}</ref> The search was extended to ''B''<SUB>50000</SUB> by Václav Kotěšovec (05/18/2021).
 
==History==
[[File:Genji chapter symbols groupings of 5 elements.svg|thumb|The traditional Japanese symbols for the 54 chapters of the ''[[Tale of Genji]]'' are based on the 52 ways of partitioning five elements (the two red symbols represent the same partition, and the green symbol is added for reaching 54).{{sfn|Knuth|2013}}]]
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]].{{sfn|Bell|1934}}{{sfn|Bell|1938}} 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 {{harvtxtharvnb|Dobiński|1877}} which gives [[Dobiński's formula]] for the Bell numbers. Bell called these numbers "exponential numbers"; the name "Bell numbers" and the notation ''B<sub>n</sub>'' for these numbers was given to them by {{harvtxtharvnb|Becker|Riordan|1948}}.<ref>{{harvnb|Rota|1964}}. However, Rota gives an incorrect date, 1934, for {{harvnb|Becker|Riordan|1948}}.</ref>
 
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 ''B''<sub>5</sub>, were recorded by 52 different diagrams, which were printed above the chapter headings in some editions of ''The Tale of Genji.''{{sfn|Knuth|2013}}<ref>{{harvnb|Gardner|1978}} and {{harvnb|Berndt|2011}} also mention the connection between Bell numbers and ''The Tale of Genji,'' in less detail.</ref>
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 ''B''<sub>5</sub>, were recorded by 52 different diagrams, which were printed above the chapter headings in some editions of The Tale of Genji.{{sfn|Knuth|2013}}<ref>{{harvnb|Gardner|1978}} and {{harvnb|Berndt|2011}} also mention the connection between Bell numbers and The Tale of Genji, in less detail.</ref>
 
In [[Srinivasa Ramanujan]]'s second notebook, he investigated both Bell polynomials and Bell numbers.{{sfn|Berndt|2011}}
Early references for the [[Bell triangle]], which has the Bell numbers on both of its sides, include {{harvtxtharvnb|Peirce|1880}} and {{harvtxtharvnb|Aitken|1933}}.
 
==See also==
Line 245 ⟶ 252:
}}
*{{cite book
| last = de Bruijn | first = N.G. | author-link = Nicolaas_Govert_de_BruijnNicolaas Govert de Bruijn
| page = 108
| title = Asymptotic methods in analysis
Line 302 ⟶ 309:
| volume = 65
| year = 1994
| doi-access = free
}}
*{{cite book
Retrieved from "https://en.wikipedia.org/wiki/Bell_number"