Editing Bell number (section)

===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}}

Therefore, using the latter formula one can compute Bell numbers non-recursively:
	
:<math>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 .</math>
	
	
Using one of the explicit formula for the [[Stirling numbers and exponential generating functions in symbolic combinatorics#Stirling numbers of the second kind|Stirling numbers of the second kind]].
<ref>{{Cite web|url=https://discrete.openmathbooks.org/more/mdm/sec_adv-stirling.html|title=Stirling Numbers of the Second Kind, Theorem 3.4.1|last=|first=|date=|website=|publisher=|access-date=}}</ref>

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

which can be generalized in this manner:<ref name=":0">{{Cite journal |last1=Komatsu |first1=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>

which 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’s formula.

===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 <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, ... {{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 {{harvnb|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>

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

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 {{harvnb|de Bruijn|1981}}.