View source for Bell number

In [[combinatorics|combinatorial mathematics]], the '''Bell numbers''' count the possible [[partition of a set|partitions 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 of [[Stigler's law of eponymy]], they are named after [[Eric Temple Bell]], who wrote about them in the 1930s.

Starting with ''B''<sub>0</sub> = ''B''<sub>1</sub> = 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, ... {{OEIS|id=A000110}}.

The ''n''th of these numbers, ''B<sub>n</sub>'', counts the number of different ways to partition a set that has exactly ''n'' elements, or equivalently, the number of [[equivalence relation]]s on it. ''B<sub>n</sub>'' also counts the number of different [[rhyme scheme]]s for ''n''-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, ''B<sub>n</sub>'' is the ''n''th moment of a [[Poisson distribution]] with [[mean]] 1.

==Counting==

===Set partitions===
{{main article|Partition of a set}}
[[File:Bell numbers subset partial order.svg|thumb|right|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.]]
[[File:Set partitions 5; circles.svg|thumb|The 52 partitions of a set with 5 elements]]
In general, ''B''<sub>''n''</sub> is the number of [[partition of a set|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, ''B''<sub>3</sub>&nbsp;=&nbsp;5 because the 3-element set {''a'',&nbsp;''b'',&nbsp;''c''} can be partitioned in 5 distinct ways:

:{ {''a''}, {''b''}, {''c''} }
:{ {''a''}, {''b'', ''c''} }
:{ {''b''}, {''a'', ''c''} }
:{ {''c''}, {''a'', ''b''} }
:{ {''a'', ''b'', ''c''} }.

''B''<sub>0</sub> is 1 because there is exactly one partition of the [[empty set]]. Every member of the empty set is a nonempty set (that is [[vacuous truth|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 [[Weak ordering|ordered partitions]] is given by the [[ordered Bell number]]s.

===Factorizations===
If a number ''N'' is a [[squarefree]] positive [[integer]] (meaning that it is the product of some number ''n'' of distinct [[prime number]]s), then ''B<sub>n</sub>'' gives the number of different [[multiplicative partition]]s of ''N''. These are [[factorization]]s of ''N'' 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 ''B''<sub>3</sub> = 5 factorizations:
:<math>30 = 2\times 15=3\times 10=5\times 6=2\times 3\times 5</math>

===Rhyme schemes===
The Bell numbers also count the [[rhyme scheme]]s 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 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.{{sfn|Gardner|1978}}

===Permutations===
The Bell numbers come up in a card [[shuffling]] problem mentioned in the addendum to {{harvtxt|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.

==Triangle scheme for calculations==
{{main article|Bell triangle}}
[[Image:BellNumberAnimated.gif|right|thumb|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]].<ref>{{Cite OEIS|A011971|name=Aitken's array}}</ref>

# Start with the number one.  Put this on a row by itself. (<math> x_{0,1} = 1 </math>)
# Start a new row with the rightmost element from the previous row as the leftmost number (<math>x_{i,1} \leftarrow x_{i-1, r}</math> where ''r'' is the last element of (''i''-1)-th row)
# 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 <math>( x_{i,j} \leftarrow x_{i,j-1} + x_{i-1,j-1} )</math> 
# Repeat step three until there is a new row with one more number than the previous row (do step 3 until <math> j = r + 1 </math>)
# The number on the left hand side of a given row is the ''Bell number'' for that row. (<math>B_i \leftarrow x_{i,1}</math>)

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 coefficient]]s:{{sfn|Wilf|1994|p=23}}
:<math>B_{n+1}=\sum_{k=0}^{n} \binom{n}{k} B_k.</math>
It can be explained by observing that, from an arbitrary partition of ''n''&nbsp;+&nbsp;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 <math>\tbinom{n}{k}</math> choices for the ''k'' items that remain after one set is removed, and ''B<sub>k</sub>'' choices of how to partition them.

A different summation formula represents  each Bell number as a sum of [[Stirling numbers of the second kind]]
:<math>B_n=\sum_{k=0}^n \left\{{n\atop k}\right\}.</math>
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}}

{{harvtxt|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>

===Generating function===
The [[generating function|exponential generating function]] of the Bell numbers is
:<math>B(x) = \sum_{n=0}^\infty \frac{B_n}{n!} x^n = e^{e^x-1}.</math>
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 uses [[analytic 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 nonempty [[Urn problem|urns]] into which elements labelled from 1 to ''n'' have been distributed, and the [[combinatorial class]] of all partitions (for all ''n'') may be expressed by the notation
:<math>\mathrm{S\scriptstyle ET}(\mathrm{S\scriptstyle ET}_{\ge 1}(\mathcal{Z})).</math>
Here, <math>\mathcal{Z}</math> is a combinatorial class with only a single member of size one, an element that can be placed into an urn. The inner <math>\mathrm{S\scriptstyle ET}_{\ge 1}</math> operator describes a set or urn that contains one or more labelled elements, and the outer
<math>\mathrm{S\scriptstyle ET}</math> describes the overall partition as a set of these urns. The exponential generating function may then be read off from this notation by translating the <math>\mathrm{S\scriptstyle ET}</math> operator into the exponential function and the nonemptiness constraint ≥1 into subtraction by one.{{sfn|Flajolet|Sedgewick|2009}}

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 the [[differential equation]] <math>B'(x) = e^{x}B(x)</math>. The function itself can be found by solving this equation.{{sfn|Rota|1964}}{{sfn|Wilf|1994|pp=20-23}}{{sfn|Bender|Williamson|2006}}

===Moments of probability distributions===
The Bell numbers satisfy [[Dobinski's formula]]{{sfn|Dobiński|1877}}{{sfn|Rota|1964}}{{sfn|Bender|Williamson|2006}}
:<math>B_n=\frac{1}{e}\sum_{k=0}^\infty \frac{k^n}{k!}.</math>
This formula can be derived by expanding the exponential generating function using the [[Taylor series]] for the exponential function, and then collecting terms with the same exponent.{{sfn|Flajolet|Sedgewick|2009}}
It allows ''B<sub>n</sub>'' to be interpreted as the ''n''th [[moment (mathematics)|moment]] of a [[Poisson distribution]] with [[expected value]] 1.

The ''n''th Bell number is also the sum of the coefficients in the ''n''th [[Bell polynomial|complete Bell polynomial]], which expresses the ''n''th [[moment (mathematics)|moment]] of any [[probability distribution]] as a function of the first ''n'' [[cumulant]]s.

===Modular arithmetic===
The Bell numbers obey [[Touchard's congruence]]: If ''p'' is any [[prime number]] then{{sfnp|Becker|Riordan|1948}}
:<math>B_{p+n} \equiv B_n+B_{n+1} \pmod p</math>
or, generalizing{{sfnp|Hurst|Schultz|2009}}
:<math>B_{p^m+n} \equiv mB_n+B_{n+1} \pmod p.</math>

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 ''p'' ≤ 101 and ''p'' = 113, 163, 167, or 173 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===
An application of [[Cauchy's integral formula]] to the exponential generating function yields the complex integral representation
: <math> B_n = \frac{n!}{2 \pi i e} \int_{\gamma} \frac{e^{e^z}}{z^{n+1}} \, dz. </math>

Some asymptotic representations can then be derived by a standard application of the [[method of steepest descent]].<ref>{{cite book|title=Complex Analysis|first=Barry|last=Simon|year=2010|contribution=Example 15.4.6 (Asymptotics of Bell Numbers)|pages=772–774|url=http://www.math.caltech.edu/~2010-11/2term/ma111b/CA-Sec15-4_march2.pdf|access-date=2012-09-02|archive-url=https://web.archive.org/web/20140124082617/http://www.math.caltech.edu/~2010-11/2term/ma111b/CA-Sec15-4_march2.pdf|archive-date=2014-01-24|url-status=dead}}</ref>

===Log-concavity===
The Bell numbers form a [[logarithmically concave sequence|logarithmically convex sequence]]. Dividing them by the factorials, ''B''<sub>''n''</sub>/''n''!, gives a logarithmically concave sequence.{{sfn|Engel|1994}}{{sfn|Canfield|1995}}{{sfn|Asai|Kubo|Kuo|2000}}

===Growth rate===
Several [[Asymptotic analysis|asymptotic]] formulas for the Bell numbers are known.  In {{harvtxt|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>,
:<math> B_n < \left( \frac{e^{-0.6 + \varepsilon} n}{\ln(n+1)}\right)^n </math>
where   <math> ~n_0(\varepsilon) = \max\left\{e^4,d^{-1}(\varepsilon) \right\}~ </math>   and
<math> ~d(x):= \ln \ln (x+1) - \ln \ln x + \frac{1+e^{-1}}{\ln x}\,.
</math>
The Bell numbers can also be approximated using the [[Lambert W function]], a function with the same growth rate as the logarithm, as {{sfnp|Lovász|1993}}
:<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>

{{harvtxt|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|accessdate=2013-10-24}}</ref>

The asymptotic expression

:<math>
\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}
</math>

was established by {{harvtxt|de Bruijn|1981}}.

==Bell primes==
{{harvtxt|Gardner|1978}} raised the question of whether infinitely many Bell numbers are also [[prime number]]s. The first few Bell numbers that are prime 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 web|url=http://primes.utm.edu/primes/page.php?id=68825|title=93074010508593618333...83885253703080601131|work=5000 Largest Known Primes, The Prime Database|accessdate=2013-10-24}}</ref> {{As of|2018}}, 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 [[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>

==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]].{{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 {{harvtxt|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 ''B<sub>n</sub>'' for these numbers was given to them by {{harvtxt|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 [[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 {{harvtxt|Peirce|1880}} and {{harvtxt|Aitken|1933}}.

==See also==
* [[Touchard polynomials]]
* [[Catalan number]]

==Notes==
{{Reflist|30em}}

==References==
{{refbegin|30em}}
*{{cite journal
 | last1 = Asai | first1 = Nobuhiro
 | last2 = Kubo | first2 = Izumi
 | last3 = Kuo | first3 = Hui-Hsiung
 | arxiv = math/0104137
 | doi = 10.1023/A:1010738827855
 | issue = 1-3
 | journal = Acta Applicandae Mathematicae
 | mr = 1831247
 | pages = 79–87
 | title = Bell numbers, log-concavity, and log-convexity
 | volume = 63
 | year = 2000
 | ref = harv}}
*{{cite journal
 | last = Aitken | first = A. C. | author-link = Alexander Aitken
 | doi = 10.1017/S1757748900002334
 | journal = [[Edinburgh Mathematical Notes|Mathematical Notes]]
 | pages = 18–23
 | title = A problem in combinations
 | volume = 28
 | year = 1933|ref=harv }}
*{{cite journal|ref=harv|first1=H. W.|last1=Becker|first2=John|last2=Riordan|author2-link=John Riordan (mathematician)|title=The arithmetic of Bell and Stirling numbers|journal=American Journal of Mathematics|volume=70|year=1948|pages=385–394|jstor= 2372336|doi=10.2307/2372336}}.
*{{cite journal|first=E. T.|last=Bell|authorlink=Eric Temple Bell|title= Exponential polynomials|journal=Annals of Mathematics|volume=35|year=1934|pages=258–277|ref=harv|jstor=1968431|doi=10.2307/1968431}}.
*{{cite journal|first=E. T.|last=Bell|authorlink=Eric Temple Bell|title= The iterated exponential integers|journal=Annals of Mathematics|volume=39|year=1938|pages=539–557|ref=harv|jstor=1968633|doi=10.2307/1968633}}.
*{{cite book
 | last1 = Bender | first1 = Edward A.
 | last2 = Williamson | first2 = S. Gill
 | contribution = Example 11.7, Set Partitions
 | isbn = 0-486-44603-4
 | pages = 319–320
 | publisher = Dover
 | title = Foundations of Combinatorics with Applications
 | url = http://www.math.ucsd.edu/~ebender/CombText/ch-11.pdf
 | year = 2006
 | ref = harv}}
*{{cite journal
 | last1 = Berend | first1 = D.
 | last2 = Tassa | first2 = T.
 | issue = 2
 | journal = Probability and Mathematical Statistics
 | pages = 185–205
 | title = Improved bounds on Bell numbers and on moments of sums of random variables
 | volume = 30
 | year = 2010
 | ref = harv}}
*{{cite journal
 | last = Berndt | first = Bruce C.
 | issue = 2
 | journal = Asia Pacific Mathematics Newsletter
 | pages = 8–13
 | title = Ramanujan Reaches His Hand From His Grave To Snatch Your Theorems From You
 | url = http://www.asiapacific-mathnews.com/01/0102/0008_0013.pdf
 | volume = 1
 | year = 2011
 | ref = harv}}
*{{cite book
 | last = de Bruijn | first = N.G. | author-link = Nicolaas_Govert_de_Bruijn
 | page = 108
 | title = Asymptotic methods in analysis
 | publisher = Dover
 | edition = 3rd
 | year = 1981
 | ref = harv}}
*{{cite journal
 | last = Callan | first = David
 | arxiv = math/0507169
 | issue = 1
 | journal = Journal of Integer Sequences
 | mr = 2193154
 | page = 06.1.4
 | title = A combinatorial interpretation of the eigensequence for composition
 | url = https://eudml.org/doc/52955
 | volume = 9
 | year = 2006
 | ref = harv|bibcode = 2005math......7169C}}
*{{cite journal
 | last = Canfield | first = E. Rodney
 | doi = 10.1016/0097-3165(95)90033-0
 | issue = 1
 | journal = Journal of Combinatorial Theory
 | mr = 1354972
 | pages = 184–187
 | series = Series A
 | title = Engel's inequality for Bell numbers
 | volume = 72
 | year = 1995
 | ref = harv}}
*{{cite journal
 | last = Claesson | first = Anders
 | doi = 10.1006/eujc.2001.0515
 | issue = 7
 | journal = European Journal of Combinatorics
 | mr = 1857258
 | pages = 961–971
 | title = Generalized pattern avoidance
 | volume = 22
 | year = 2001
 | ref = harv| arxiv = math/0011235
 }}
*{{cite book|last1=Conway|first1=John Horton|author1-link=John Horton Conway|last2=Guy|first2=Richard K.|author2-link=Richard K. Guy|title=The Book of Numbers|series=Copernicus Series|publisher=Springer|year=1996|isbn=9780387979939|contribution=Famous Families of Numbers: Bell Numbers and Stirling Numbers|pages=91–94|ref=harv}}
*{{cite journal|first=G.|last=Dobiński|title=Summirung<!-- "Summirung" is an archaic spelling, and it is the spelling that was used in this title. --> der Reihe <math>\textstyle\sum\frac{n^m}{n!}</math> für ''m''&nbsp;=&nbsp;1,&nbsp;2,&nbsp;3,&nbsp;4,&nbsp;5,&nbsp;…|journal=Grunert's Archiv|volume=61|year=1877|pages=333–336|url=https://archive.org/stream/archivdermathem88unkngoog#page/n346|ref=harv}}
*{{cite journal
 | last = Engel | first = Konrad
 | doi = 10.1016/0097-3165(94)90038-8
 | issue = 1
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 1255264
 | pages = 67–78
 | series = Series A
 | title = On the average rank of an element in a filter of the partition lattice
 | volume = 65
 | year = 1994
 | ref = harv}}
*{{cite book
 | last1 = Flajolet | first1 = Philippe | author1-link = Philippe Flajolet
 | last2 = Sedgewick | first2 = Robert | author2-link = Robert Sedgewick (computer scientist)
 | contribution = II.3 Surjections, set partitions, and words
 | pages = 106–119
 | publisher = Cambridge University Press
 | title = Analytic Combinatorics
 | url = http://algo.inria.fr/flajolet/Publications/book.pdf
 | year = 2009
 | ref = harv}}
*{{cite journal
 | last = Gardner | first = Martin | author-link = Martin Gardner
 | doi = 10.1038/scientificamerican0578-24
 | journal = [[Scientific American]]
 | pages = 24–30
 | title = The Bells: versatile numbers that can count partitions of a set, primes and even rhymes
 | volume = 238
 | year = 1978|ref=harv| bibcode = 1978SciAm.238e..24G}} 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.&nbsp;24–38
* {{springer|title=Bell numbers|id=p/b110240}}
*{{cite arXiv|title=An elementary (number theory) proof of Touchard's congruence|first1=Greg|last1=Hurst|first2=Andrew|last2=Schultz|eprint=0906.0696|year=2009|class=math.CO|ref=harv}}
* {{cite book|contribution=Two thousand years of combinatorics|first=Donald E.|last=Knuth|authorlink=Donald Knuth|pages=7–37|title=Combinatorics: Ancient and Modern|publisher=Oxford University Press|year=2013|editor1-first=Robin|editor1-last=Wilson|editor2-first=John J.|editor2-last=Watkins|ref=harv}}
*{{Cite book |authorlink=László Lovász| last=Lovász | first=L. |title=Combinatorial Problems and Exercises |edition=2nd |place=Amsterdam, Netherlands |publisher=North-Holland |year=1993|zbl=0785.05001|contribution=Section 1.14, Problem 9|page=17|url=https://books.google.com/books?id=e99fXXYx9zcC&pg=PA17|ref=harv}}
*{{cite journal
 | last1 = Moser | first1 = Leo | author1-link = Leo Moser
 | last2 = Wyman | first2 = Max
 | journal = Transactions of the Royal Society of Canada, Section III
 | mr = 0078489
 | pages = 49–54
 | title = An asymptotic formula for the Bell numbers
 | volume = 49
 | year = 1955
 | ref = harv}}
*{{cite journal
 | last = Peirce | first = C. S. | author-link = Charles Sanders Peirce
 | issue = 1
 | journal = [[American Journal of Mathematics]]
 | jstor = 2369442
 | pages = 15–57
 | title = On the algebra of logic
 | volume = 3
 | year = 1880|ref=harv | doi=10.2307/2369442}}. 
*{{citation
 | last = Rota | first = Gian-Carlo | author-link = Gian-Carlo Rota
 | doi = 10.2307/2312585
 | issue = 5
 | journal = [[American Mathematical Monthly]]
 | mr = 0161805
 | pages = 498–504
 | title = The number of partitions of a set
 | volume = 71
 | year = 1964
 | ref = harv}}
*{{cite journal
 | last = Spivey | first = Michael Z.
 | issue = 2
 | journal = Journal of Integer Sequences
 | mr = 2420912
 | page = Article 08.2.5, 3
 | title = A generalized recurrence for Bell numbers
 | url = http://www.cs.uwaterloo.ca/journals/JIS/VOL11/Spivey/spivey25.pdf
 | volume = 11
 | year = 2008
 | ref = harv}}
*{{cite journal
 | last = Wagstaff | first = Samuel S. | author-link = Sam Wagstaff
 | bibcode = 1996MaCom..65..383W
 | doi = 10.1090/S0025-5718-96-00683-7
 | issue = 213
 | journal = [[Mathematics of Computation]]
 | mr = 1325876
 | pages = 383–391
 | title = Aurifeuillian factorizations and the period of the Bell numbers modulo a prime
 | url = http://homes.cerias.purdue.edu/~ssw/bell/bell.ps
 | volume = 65
 | year = 1996
 | ref = harv}}
* {{cite book | last=Wilf | first=Herbert S. | authorlink=Herbert Wilf | title=Generatingfunctionology | edition=2nd | location=Boston, MA | publisher=Academic Press | year=1994 | isbn=0-12-751956-4 | zbl=0831.05001 |ref=harv | url = https://www.math.upenn.edu/~wilf/gfology2.pdf
}}
*{{cite journal
 | last = Williams | first = G. T.
 | journal = [[American Mathematical Monthly]]
 | jstor = 2305292
 | doi = 10.2307/2305292
 | mr = 0012612
 | pages = 323–327
 | title = Numbers generated by the function ''e''<sup>''e''<sup>''x''</sup>&nbsp;&minus;&nbsp;1</sup>
  | volume = 52
 | year = 1945
 | ref = harv}}
{{refend}}

==External links==
* {{Cite web
|author=Robert Dickau
|url=http://mathforum.org/advanced/robertd/bell.html
|title=Diagrams of Bell numbers
}}
* {{MathWorld|urlname=BellNumber|title=Bell Number
}}
* {{Cite web
|author=Gottfried Helms
|url=http://go.helms-net.de/math/binomial/04_5_SummingBellStirling.pdf
|title=Further properties & Generalization of Bell-Numbers
}}

{{Classes of natural numbers}}

{{DEFAULTSORT:Bell Number}}
[[Category:Integer sequences]]