Movatterモバイル変換

[0]ホーム
URL:

Jump to content
WikipediaThe Free Encyclopedia
Search

Bell number

From Wikipedia, the free encyclopedia
(Redirected fromBell numbers)
Count of the possible partitions of a set
Not to be confused withPell number.

Incombinatorial mathematics, theBell numbers count the possiblepartitions of a set. These numbers have been studied by mathematicians since the 19th century, and their roots go back to medieval Japan. In an example ofStigler's law of eponymy, they are named afterEric Temple Bell, who wrote about them in the 1930s.

The Bell numbers are denotedBn{\displaystyle B_{n}}, wheren{\displaystyle n} is aninteger greater than or equal tozero. Starting withB0=B1=1{\displaystyle B_{0}=B_{1}=1}, the first few Bell numbers are

1,1,2,5,15,52,203,877,4140,…{\displaystyle 1,1,2,5,15,52,203,877,4140,\dots } (sequenceA000110 in theOEIS).

The Bell numberBn{\displaystyle B_{n}} counts the different ways to partition a set that has exactlyn{\displaystyle n} elements, or equivalently, theequivalence relations on it.Bn{\displaystyle B_{n}} also counts the differentrhyme schemes forn{\displaystyle n}-line poems.[1]

As well as appearing in counting problems, these numbers have a different interpretation, asmoments ofprobability distributions. In particular,Bn{\displaystyle B_{n}} is then{\displaystyle n}-th moment of aPoisson distribution withmean 1.

Counting

[edit]

Set partitions

[edit]
Main article:Partition of a set
The 52 partitions of a set with 5 elements

In general,Bn{\displaystyle B_{n}} is the number of partitions of a set of sizen{\displaystyle n}. A partition of a setS{\displaystyle S} is defined as a family of nonempty, pairwise disjoint subsets ofS{\displaystyle S} whose union isS{\displaystyle S}. For example,B3=5{\displaystyle B_{3}=5} because the 3-element set{a,b,c}{\displaystyle \{a,b,c\}} can be partitioned in 5 distinct ways:

{{a},{b},{c}},{\displaystyle \{\{a\},\{b\},\{c\}\},}
{{a},{b,c}},{\displaystyle \{\{a\},\{b,c\}\},}
{{b},{a,c}},{\displaystyle \{\{b\},\{a,c\}\},}
{{c},{a,b}},{\displaystyle \{\{c\},\{a,b\}\},}
{{a,b,c}}.{\displaystyle \{\{a,b,c\}\}.}

As suggested by the set notation above, the ordering of subsets within the family is not considered;ordered partitions are counted by a different sequence of numbers, theordered Bell numbers.B0{\displaystyle B_{0}} is 1 because there is exactly one partition of theempty set. This partition is itself the empty set; it can be interpreted as a family of subsets of the empty set, consisting of zero subsets. It isvacuously true that all of the subsets in this family are non-empty subsets of the empty set and that they are pairwise disjoint subsets of the empty set, because there are no subsets to have these unlikely properties.

The partitions of a setcorrespond one-to-one with itsequivalence relations. These arebinary relations that arereflexive,symmetric, andtransitive. The equivalence relation corresponding to a partition defines two elements as being equivalent when they belong to the same partition subset as each other. Conversely, every equivalence relation corresponds to a partition intoequivalence classes.[2] Therefore, the Bell numbers also count the equivalence relations.

Factorizations

[edit]

If a numberN{\displaystyle N} is asquarefree positiveinteger, meaning that it is the product of some numbern{\displaystyle n} of distinctprime numbers, thenBn{\displaystyle B_{n}} gives the number of differentmultiplicative partitions ofN{\displaystyle N}. These arefactorizations ofN{\displaystyle N} into numbers greater than one, treating two factorizations as the same if they have the same factors in a different order.[3] For instance, 30 is the product of the three primes 2, 3, and 5, and hasB3{\displaystyle B_{3}} = 5 factorizations:

30=2×15=3×10=5×6=2×3×5{\displaystyle 30=2\times 15=3\times 10=5\times 6=2\times 3\times 5}

Rhyme schemes

[edit]

The Bell numbers also count therhyme schemes of ann-linepoem orstanza. 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 a 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

[edit]

The Bell numbers come up in a cardshuffling problem mentioned in the addendum toGardner 1978. If a deck ofn 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 exactlyn repetitions of this operation, then there arenn different shuffles that can be performed. Of these, the number that return the deck to its original sorted order is exactlyBn. Thus, the probability that the deck is in its original order after shuffling it in this way isBn/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 ofpermutations that are also answered by the Bell numbers. For instance, thenth Bell number equals the number of permutations onn items in which no three values that are in sorted order have the last two of these three consecutive. In a notation for generalizedpermutation 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.[4] 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.[5] 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

[edit]
Main article:Bell triangle
The triangular array whose right-hand diagonal sequence consists of Bell numbers

The Bell numbers can easily be calculated by creating the so-calledBell triangle, also calledAitken's array or thePeirce triangle afterAlexander Aitken andCharles Sanders Peirce.[6]

  1. Start with the number one. Put this on a row by itself. (x0,1=1{\displaystyle x_{0,1}=1})
  2. Start a new row with the rightmost element from the previous row as the leftmost number (xi,1←xi−1,r{\displaystyle x_{i,1}\leftarrow x_{i-1,r}} wherer is the last element of (i − 1)-th row)
  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, that is, the number diagonally up and left of the number we are calculating(xi,j←xi,j−1+xi−1,j−1){\displaystyle (x_{i,j}\leftarrow x_{i,j-1}+x_{i-1,j-1})}
  4. Repeat step three until there is a new row with one more number than the previous row (do step 3 untilj=r+1{\displaystyle j=r+1})
  5. The number on the left hand side of a given row is theBell number for that row. (Bi←xi,1{\displaystyle B_{i}\leftarrow x_{i,1}})

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

1122355710151520273752{\displaystyle {\begin{array}{l}1\\1&2\\2&3&5\\5&7&10&15\\15&20&27&37&52\end{array}}}

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

Properties

[edit]

Summation formulas

[edit]

The Bell numbers satisfy arecurrence relation involvingbinomial coefficients:[7]

Bn+1=∑k=0n(nk)Bk.{\displaystyle B_{n+1}=\sum _{k=0}^{n}{\binom {n}{k}}B_{k}.}

It can be explained by observing that, from an arbitrary partition ofn + 1 items, removing the set containing the first item leaves a partition of a smaller set ofk items for some numberk that may range from 0 ton. There are(nk){\displaystyle {\tbinom {n}{k}}} choices for thek items that remain after one set is removed, andBk choices of how to partition them.

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

Bn=∑k=0n{nk}.{\displaystyle B_{n}=\sum _{k=0}^{n}\left\{{n \atop k}\right\}.}

The Stirling number{nk}{\displaystyle \left\{{n \atop k}\right\}} is the number of ways to partition a set of cardinalityn into exactlyk 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 whichk is the number of sets in the partition.[8]

Therefore, using the latter formula one can compute Bell numbers non-recursively as

Bn=∑k=0n{nk}=∑k=0n1k!∑i=0k(−1)k−i(ki)in,{\displaystyle B_{n}=\sum _{k=0}^{n}\left\{{n \atop k}\right\}=\sum _{k=0}^{n}{\frac {1}{k!}}\sum _{i=0}^{k}(-1)^{k-i}{\binom {k}{i}}i^{n},}

using one of the explicit formula for the Stirling numbers of the second kind.[9]

Spivey 2008 has given a formula that combines both of these summations:

Bn+m=∑k=0n∑j=0m{mj}(nk)jn−kBk.{\displaystyle B_{n+m}=\sum _{k=0}^{n}\sum _{j=0}^{m}\left\{{m \atop j}\right\}{n \choose k}j^{n-k}B_{k}.}

ApplyingPascal's inversion formula to the recurrence relation, we obtain

Bn=∑k=0n(nk)(−1)n−kBk+1,{\displaystyle B_{n}=\sum _{k=0}^{n}{\binom {n}{k}}(-1)^{n-k}B_{k+1},}

which can be generalized in this manner:[10]

∑j=0n(nj)Bk+j=∑i=0k(ki)(−1)k−iBn+i+1.{\displaystyle \sum _{j=0}^{n}{\binom {n}{j}}B_{k+j}=\sum _{i=0}^{k}{\binom {k}{i}}(-1)^{k-i}B_{n+i+1}.}

Other finite sum formulas usingStirling numbers of the first kind include[10]

∑j=0n(nj)ajbn−jBj=∑i=0k[ki](−1)k−i∑j=0n(nj)aj(b−ak)n−jBj+i,{\displaystyle \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},}

which simplifies down withk=1{\displaystyle k=1} to

∑j=0n(nj)ajbn−jBj=∑j=0n(nj)aj(b−a)n−jBj+1{\displaystyle \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}}

and witha=1{\displaystyle a=1},b=k{\displaystyle b=k} to

∑j=0n(nj)Bjkn−j=∑i=0k[ki]Bn+i(−1)k−i{\displaystyle \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}}which can be seen as theinversion formula for Stirling numbers applied to Spivey’s formula.

Generating function

[edit]

Theexponential generating function of the Bell numbers is

B(x)=∑n=0∞Bnn!xn=eex−1.{\displaystyle B(x)=\sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}x^{n}=e^{e^{x}-1}.}

In this formula, the summation in the middle is the general form used to define the exponential generating function for any sequence of numbers, and the formula on the right is the result of performing the summation in the specific case of the Bell numbers.

One way to derive this result usesanalytic combinatorics, a style of mathematical reasoning in which sets of mathematical objects are described by formulas explaining their construction from simpler objects, and then those formulas are manipulated to derive the combinatorial properties of the objects. In the language of analytic combinatorics, a set partition may be described as a set of nonemptyurns into which elements labelled from 1 ton have been distributed, and thecombinatorial class of all partitions (for alln) may be expressed by the notation

SET(SET≥1(Z)).{\displaystyle \mathrm {S\scriptstyle ET} (\mathrm {S\scriptstyle ET} _{\geq 1}({\mathcal {Z}})).}

Here,Z{\displaystyle {\mathcal {Z}}} is a combinatorial class with only a single member of size one, an element that can be placed into an urn. The innerSET≥1{\displaystyle \mathrm {S\scriptstyle ET} _{\geq 1}} operator describes a set or urn that contains one or more labelled elements, and the outerSET{\displaystyle \mathrm {S\scriptstyle ET} } describes the overall partition as a set of these urns. The exponential generating function may then be read off from this notation by translating theSET{\displaystyle \mathrm {S\scriptstyle ET} } operator into the exponential function and the nonemptiness constraint ≥1 into subtraction by one.[11]

An alternative method for deriving the same generating function uses the recurrence relation for the Bell numbers in terms of binomial coefficients to show that the exponential generating function satisfies thedifferential equationB′(x)=exB(x){\displaystyle B'(x)=e^{x}B(x)}. The function itself can be found by solving this equation.[12][13][14]

Moments of probability distributions

[edit]

The Bell numbers satisfyDobinski's formula[15][12][14]

Bn=1e∑k=0∞knk!.{\displaystyle B_{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}}.}

This formula can be derived by expanding the exponential generating function using theTaylor series for the exponential function, and then collecting terms with the same exponent.[11]It allowsBn to be interpreted as thenthmoment of aPoisson distribution withexpected value 1.

Thenth Bell number is also the sum of the coefficients in thenthcomplete Bell polynomial, which expresses thenthmoment of anyprobability distribution as a function of the firstncumulants.

Modular arithmetic

[edit]

The Bell numbers obeyTouchard's congruence: Ifp is anyprime number then[16]

Bp+n≡Bn+Bn+1(modp){\displaystyle B_{p+n}\equiv B_{n}+B_{n+1}{\pmod {p}}}

or, generalizing[17]

Bpm+n≡mBn+Bn+1(modp).{\displaystyle B_{p^{m}+n}\equiv mB_{n}+B_{n+1}{\pmod {p}}.}

Because of Touchard's congruence, the Bell numbers are periodic modulop, for every prime numberp; for instance, forp = 2, the Bell numbers repeat the pattern odd-odd-even with period three. The period of this repetition, for an arbitrary prime numberp, must be a divisor of

pp−1p−1{\displaystyle {\frac {p^{p}-1}{p-1}}}

and for all primep≤101{\displaystyle p\leq 101} andp=113,163,167{\displaystyle p=113,163,167}, or173{\displaystyle 173} it is exactly this number (sequenceA001039 in theOEIS).[18][19]

The period of the Bell numbers to modulon are

1, 3, 13, 12, 781, 39, 137257, 24, 39, 2343, 28531167061, 156, ... (sequenceA054767 in theOEIS)

Integral representation

[edit]

An application ofCauchy's integral formula to the exponential generating function yields the complex integral representation

Bn=n!2πie∫γeezzn+1dz.{\displaystyle B_{n}={\frac {n!}{2\pi ie}}\int _{\gamma }{\frac {e^{e^{z}}}{z^{n+1}}}\,dz.}

Some asymptotic representations can then be derived by a standard application of themethod of steepest descent.[20]

Log-concavity

[edit]

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

Growth rate

[edit]

Severalasymptotic formulas for the Bell numbers are known. InBerend & Tassa 2010 the following bounds were established:

Bn<(0.792nln⁡(n+1))n{\displaystyle B_{n}<\left({\frac {0.792n}{\ln(n+1)}}\right)^{n}} for all positive integersn{\displaystyle n};

moreover, ifε>0{\displaystyle \varepsilon >0} then for alln>n0(ε){\displaystyle n>n_{0}(\varepsilon )},

Bn<(e−0.6+εnln⁡(n+1))n{\displaystyle B_{n}<\left({\frac {e^{-0.6+\varepsilon }n}{\ln(n+1)}}\right)^{n}}

where n0(ε)=max{e4,d−1(ε)} {\displaystyle ~n_{0}(\varepsilon )=\max \left\{e^{4},d^{-1}(\varepsilon )\right\}~} and d(x):=ln⁡ln⁡(x+1)−ln⁡ln⁡x+1+e−1ln⁡x.{\displaystyle ~d(x):=\ln \ln(x+1)-\ln \ln x+{\frac {1+e^{-1}}{\ln x}}\,.}The Bell numbers can also be approximated using theLambert W function, a function with the same growth rate as the logarithm, as[24]

Bn∼1n(nW(n))n+12exp⁡(nW(n)−n−1).{\displaystyle 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

Bn+h=(n+h)!W(n)n+h×exp⁡(eW(n)−1)(2πB)1/2×(1+P0+hP1+h2P2eW(n)+Q0+hQ1+h2Q2+h3Q3+h4Q4e2W(n)+O(e−3W(n))){\displaystyle 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^{2}P_{2}}{e^{W(n)}}}+{\frac {Q_{0}+hQ_{1}+h^{2}Q_{2}+h^{3}Q_{3}+h^{4}Q_{4}}{e^{2W(n)}}}+O(e^{-3W(n)})\right)}

uniformly forh=O(ln⁡(n)){\displaystyle h=O(\ln(n))} asn→∞{\displaystyle n\rightarrow \infty }, whereB{\displaystyle B} and eachPi{\displaystyle P_{i}} andQi{\displaystyle Q_{i}} are known expressions inW(n){\displaystyle W(n)}.[25]

The asymptotic expression

ln⁡Bnn=ln⁡n−ln⁡ln⁡n−1+ln⁡ln⁡nln⁡n+1ln⁡n+12(ln⁡ln⁡nln⁡n)2+O(ln⁡ln⁡n(ln⁡n)2)as n→∞{\displaystyle {\begin{aligned}{\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{aligned}}}

was established byde Bruijn 1981.

Bell primes

[edit]

Gardner 1978 raised the question of whether infinitely many Bell numbers are alsoprime numbers. These are calledBell primes. The first few Bell primes are:

2, 5, 877, 27644437, 35742549198872617291353508656626642567, 359334085968622831041960188598043661065388726959079837 (sequenceA051131 in theOEIS)

corresponding to the indices 2, 3, 7, 13, 42 and 55 (sequenceA051130 in theOEIS). The nextBell prime isB2841, which is approximately 9.30740105 × 106538.[26]

History

[edit]
The traditional Japanese symbols for the 54 chapters of theTale 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).[27]

The Bell numbers are named afterEric Temple Bell, who wrote about them in 1938, following up a 1934 paper in which he studied theBell polynomials.[28][29] 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 withDobiński 1877 which givesDobiński's formula for the Bell numbers. Bell called these numbers "exponential numbers"; the name "Bell numbers" and the notationBn for these numbers was given to them byBecker & Riordan 1948.[30]

The first exhaustive enumeration of set partitions appears to have occurred in medieval Japan, where (inspired by the popularity of the bookThe Tale of Genji) a parlor game calledgenjikō 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 numberB5, were recorded by 52 different diagrams, which were printed above the chapter headings in some editions ofThe Tale of Genji.[27][31]

InSrinivasa Ramanujan's second notebook, he investigated both Bell polynomials and Bell numbers.[32]Early references for theBell triangle, which has the Bell numbers on both of its sides, includePeirce 1880 andAitken 1933.

See also

[edit]

Notes

[edit]
  1. ^abGardner 1978.
  2. ^Halmos, Paul R. (1974).Naive set theory. Undergraduate Texts in Mathematics. Springer-Verlag, New York-Heidelberg. pp. 27–28.ISBN 9781475716450.MR 0453532.
  3. ^Williams 1945 credits this observation to Silvio Minetola'sPrincipii di Analisi Combinatoria (1909).
  4. ^Claesson (2001).
  5. ^Callan (2006).
  6. ^Sloane, N. J. A. (ed.)."Sequence A011971 (Aitken's array)".TheOn-Line Encyclopedia of Integer Sequences. OEIS Foundation.
  7. ^Wilf 1994, p. 23.
  8. ^Conway & Guy (1996).
  9. ^"Stirling Numbers of the Second Kind, Theorem 3.4.1".
  10. ^abKomatsu, Takao; Pita-Ruiz, Claudio (2018)."Some formulas for Bell numbers".Filomat.32 (11):3881–3889.doi:10.2298/FIL1811881K.ISSN 0354-5180.
  11. ^abFlajolet & Sedgewick 2009.
  12. ^abRota 1964.
  13. ^Wilf 1994, pp. 20–23.
  14. ^abBender & Williamson 2006.
  15. ^Dobiński 1877.
  16. ^Becker & Riordan (1948).
  17. ^Hurst & Schultz (2009).
  18. ^Williams 1945.
  19. ^Wagstaff 1996.
  20. ^Simon, Barry (2010). "Example 15.4.6 (Asymptotics of Bell Numbers)".Complex Analysis(PDF). pp. 772–774. Archived fromthe original(PDF) on 2014-01-24. Retrieved2012-09-02.
  21. ^Engel 1994.
  22. ^Canfield 1995.
  23. ^Asai, Kubo & Kuo 2000.
  24. ^Lovász (1993).
  25. ^Canfield, Rod (July 1994)."The Moser-Wyman expansion of the Bell numbers"(PDF). Retrieved2013-10-24.
  26. ^Sloane, N. J. A. (ed.)."Sequence A051131".TheOn-Line Encyclopedia of Integer Sequences. OEIS Foundation.
  27. ^abKnuth 2013.
  28. ^Bell 1934.
  29. ^Bell 1938.
  30. ^Rota 1964. However, Rota gives an incorrect date, 1934, forBecker & Riordan 1948.
  31. ^Gardner 1978 andBerndt 2011 also mention the connection between Bell numbers andThe Tale of Genji, in less detail.
  32. ^Berndt 2011.

References

[edit]

External links

[edit]
Classes ofnatural numbers
Powers and related numbers
Of the forma × 2b ± 1
Other polynomial numbers
Recursively defined numbers
Possessing a specific set of other numbers
Expressible via specific sums
2-dimensional
centered
non-centered
3-dimensional
centered
non-centered
pyramidal
4-dimensional
non-centered
Combinatorial numbers
Divisor functions
Prime omega functions
Euler's totient function
Aliquot sequences
Primorial
Otherprime factor ordivisor related numbers
Numeral system-dependent numbers
Arithmetic functions
anddynamics
Digit sum
Digit product
Coding-related
Other
P-adic numbers-related
Digit-composition related
Digit-permutation related
Divisor-related
Other
Generated via asieve
Sorting related
Graphemics related
Retrieved from "https://en.wikipedia.org/w/index.php?title=Bell_number&oldid=1317813691"
Category:
Hidden categories:
[8]ページ先頭
©2009-2026 Movatter.jp