Fungrim home page

Bell numbers

Table of contents: Definitions - Domain and codomain - Specific values - Infinite series representations - Sum representations - Generating functions - Integral representations - Asymptotics - Bounds and inequalities - Divisibility properties - Matrix fomulas - Related topics

Definitions

1706bb
Symbol: BellNumber — BnB_{n} — Bell number
60dc3e
Bn=A000110 ⁣(n)B_{n} = \text{A000110}\!\left(n\right)

Domain and codomain

16fe51
n∈Z≥0    ⟹    Bn∈Z≥1n \in \mathbb{Z}_{\ge 0} \;\implies\; B_{n} \in \mathbb{Z}_{\ge 1}

Specific values

First cases as set partitions

4b4816
B0=#{{{}}}=1B_{0} = \# \left\{\left\{\left\{\right\}\right\}\right\} = 1
534f7d
B1=#{{{1}}}=1B_{1} = \# \left\{\left\{\left\{1\right\}\right\}\right\} = 1
3627de
B2=#{{{1},{2}},{{1,2}}}=2B_{2} = \# \left\{\left\{\left\{1\right\}, \left\{2\right\}\right\}, \left\{\left\{1, 2\right\}\right\}\right\} = 2
92cc17
B3=#{{{1},{2},{3}},{{1},{2,3}},{{2},{1,3}},{{3},{1,2}},{{1,2,3}}}=5B_{3} = \# \left\{\left\{\left\{1\right\}, \left\{2\right\}, \left\{3\right\}\right\}, \left\{\left\{1\right\}, \left\{2, 3\right\}\right\}, \left\{\left\{2\right\}, \left\{1, 3\right\}\right\}, \left\{\left\{3\right\}, \left\{1, 2\right\}\right\}, \left\{\left\{1, 2, 3\right\}\right\}\right\} = 5

Tables

4c6267
Table of BnB_{n} for 0≤n≤400 \le n \le 40
7466a2
Table of B10nB_{{10}^{n}} to 50 digits for 0≤n≤200 \le n \le 20

Infinite series representations

050c46
Bn=1e∑k=0∞knk!B_{n} = \frac{1}{e} \sum_{k=0}^{\infty} \frac{{k}^{n}}{k !}

Sum representations

948167
Bn=∑k=0n{nk}B_{n} = \sum_{k=0}^{n} \left\{{n \atop k}\right\}
4b65d0
Bn=∑k=1nknk!∑j=0n−k(−1)jj!B_{n} = \sum_{k=1}^{n} \frac{{k}^{n}}{k !} \sum_{j=0}^{n - k} \frac{{\left(-1\right)}^{j}}{j !}
1026e3
Bn+1=∑k=0n(nk)BkB_{n + 1} = \sum_{k=0}^{n} {n \choose k} B_{k}

Generating functions

9d666f
∑n=0∞Bnxn=∑k=0∞xk∏j=1k(1−jx)\sum_{n=0}^{\infty} B_{n} {x}^{n} = \sum_{k=0}^{\infty} \frac{{x}^{k}}{\prod_{j=1}^{k} \left(1 - j x\right)}
aab4e3
∑n=0∞Bnn!xn=exp⁡ ⁣(ex−1)\sum_{n=0}^{\infty} \frac{B_{n}}{n !} {x}^{n} = \exp\!\left({e}^{x} - 1\right)

Integral representations

f4e249
Bn=2n!πeIm⁡ ⁣(∫0πeeeixsin⁡ ⁣(nx) dx)B_{n} = \frac{2 n !}{\pi e} \operatorname{Im}\!\left(\int_{0}^{\pi} {e}^{{e}^{{e}^{i x}}} \sin\!\left(n x\right) \, dx\right)
a71381
Bn=2n!πe∫0πeecos⁡(x)cos⁡(sin⁡(x))sin⁡ ⁣(ecos⁡(x)sin⁡ ⁣(sin⁡(x)))sin⁡ ⁣(nx) dxB_{n} = \frac{2 n !}{\pi e} \int_{0}^{\pi} {e}^{{e}^{\cos(x)} \cos\left(\sin(x)\right)} \sin\!\left({e}^{\cos(x)} \sin\!\left(\sin(x)\right)\right) \sin\!\left(n x\right) \, dx

Asymptotics

343946
log⁡ ⁣(Bn)n∼log⁡(n)−log⁡ ⁣(log⁡(n))−1+log⁡ ⁣(log⁡(n))log⁡(n)+1log⁡(n)+12(log⁡ ⁣(log⁡(n))log⁡(n))2,  n→∞\frac{\log\!\left(B_{n}\right)}{n} \sim \log(n) - \log\!\left(\log(n)\right) - 1 + \frac{\log\!\left(\log(n)\right)}{\log(n)} + \frac{1}{\log(n)} + \frac{1}{2} {\left(\frac{\log\!\left(\log(n)\right)}{\log(n)}\right)}^{2}, \; n \to \infty
589758
Bn∼n−1/2(nW ⁣(n))n+1/2exp⁡ ⁣(nW ⁣(n)−n−1),  n→∞B_{n} \sim {n}^{-1 / 2} {\left(\frac{n}{W\!\left(n\right)}\right)}^{n + 1 / 2} \exp\!\left(\frac{n}{W\!\left(n\right)} - n - 1\right), \; n \to \infty

Bounds and inequalities

Monotonicity and convexity

2e576e
Bn+1≥BnB_{n + 1} \ge B_{n}
320dc9
Bn+1>BnB_{n + 1} > B_{n}
fb6ce2
Bn+1<nBnB_{n + 1} < n B_{n}
46bc62
Bn+1≥2BnB_{n + 1} \ge 2 B_{n}
1e00d2
Bn2≤Bn−1Bn+1≤(1+1n)Bn2B_{n}^{2} \le B_{n - 1} B_{n + 1} \le \left(1 + \frac{1}{n}\right) B_{n}^{2}
d1438d
BnBm≤Bn+m≤(n+mn)BnBmB_{n} B_{m} \le B_{n + m} \le {n + m \choose n} B_{n} B_{m}

Upper bounds

d1f218
Bn≤n!B_{n} \le n !
512beb
Bn≤(0.792nlog⁡ ⁣(n+1))nB_{n} \le {\left(\frac{0.792 n}{\log\!\left(n + 1\right)}\right)}^{n}

Lower bounds

7e449a
Bn≥en−2B_{n} \ge {e}^{n - 2}
a747a4
Bn≥kn−kB_{n} \ge {k}^{n - k}
468def
Bn≥(nelog⁡(n))nB_{n} \ge {\left(\frac{n}{e \log(n)}\right)}^{n}
b29b24
Bn≥p(n)B_{n} \ge p(n)

Divisibility properties

Touchard's congruence

60740b
Bp≡2(modp)B_{p} \equiv 2 \pmod {p}
dd9d26
Bn+p≡Bn+Bn+1(modp)B_{n + p} \equiv B_{n} + B_{n + 1} \pmod {p}
b41c49
Bn+pm≡mBn+Bn+1(modp)B_{n + {p}^{m}} \equiv m B_{n} + B_{n + 1} \pmod {p}

Periodicity

050ee1
Bn≡{0,n≡2(mod3)1,otherwise(mod2)B_{n} \equiv \begin{cases} 0, & n \equiv 2 \pmod {3}\\1, & \text{otherwise}\\ \end{cases} \pmod {2}
a4d6fc
Bn+a≡Bn(modm)   where a={3,m=213,m=312,m=4781,m=539,m=6B_{n + a} \equiv B_{n} \pmod {m}\; \text{ where } a = \begin{cases} 3, & m = 2\\13, & m = 3\\12, & m = 4\\781, & m = 5\\39, & m = 6\\ \end{cases}
b7e899
Bn+a≡Bn(modm)   where a=A054767 ⁣(m)B_{n + a} \equiv B_{n} \pmod {m}\; \text{ where } a = \text{A054767}\!\left(m\right)

Prime values

a1108d
n∈{2,3,7,13,42,55,2841}    ⟹    Bn∈Pn \in \left\{2, 3, 7, 13, 42, 55, 2841\right\} \;\implies\; B_{n} \in \mathbb{P}

Matrix fomulas

b5a382
Bn=exp⁡ ⁣(((00)(01)⋯(0N)(10)(11)⋯(1N)⋮⋮⋱⋮(N0)(N1)…(NN))−IN+1)(n+1,1)B_{n} = {\exp\!\left(\displaystyle{\begin{pmatrix} {0 \choose 0} & {0 \choose 1} & \cdots & {0 \choose N} \\ {1 \choose 0} & {1 \choose 1} & \cdots & {1 \choose N} \\ \vdots & \vdots & \ddots & \vdots \\ {N \choose 0} & {N \choose 1} & \ldots & {N \choose N} \end{pmatrix}} - I_{N + 1}\right)}_{\left(n + 1, 1\right)}
dc6806
det⁡(B0+0B0+1⋯B0+nB1+0B1+1⋯B1+n⋮⋮⋱⋮Bn+0Bn+1…Bn+n)=∏k=1nk!=G ⁣(n+2)\operatorname{det}\displaystyle{\begin{pmatrix} B_{0 + 0} & B_{0 + 1} & \cdots & B_{0 + n} \\ B_{1 + 0} & B_{1 + 1} & \cdots & B_{1 + n} \\ \vdots & \vdots & \ddots & \vdots \\ B_{n + 0} & B_{n + 1} & \ldots & B_{n + n} \end{pmatrix}} = \prod_{k=1}^{n} k ! = G\!\left(n + 2\right)
Restricted set partitions: Stirling numbers
Integer partitions: Partition function

Copyright (C) Fredrik Johansson and contributors. Fungrim is provided under the MIT license. The source code is on GitHub.

2021-03-15 19:12:00.328586 UTC