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
nZ0        BnZ1n \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 0n400 \le n \le 40
7466a2
Table of B10nB_{{10}^{n}} to 50 digits for 0n200 \le n \le 20

Infinite series representations

050c46
Bn=1ek=0knk!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=0nk(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=0Bnxn=k=0xkj=1k(1jx)\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=0Bnn!xn=exp ⁣(ex1)\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!πe0π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)nlog(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
Bnn1/2(nW0 ⁣(n))n+1/2exp ⁣(nW0 ⁣(n)n1),  nB_{n} \sim {n}^{-1 / 2} {\left(\frac{n}{W_{0}\!\left(n\right)}\right)}^{n + 1 / 2} \exp\!\left(\frac{n}{W_{0}\!\left(n\right)} - n - 1\right), \; n \to \infty

Bounds and inequalities

Monotonicity and convexity

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

Upper bounds

d1f218
Bnn!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
Bnen2B_{n} \ge {e}^{n - 2}
a747a4
BnknkB_{n} \ge {k}^{n - k}
468def
Bn(nelog(n))nB_{n} \ge {\left(\frac{n}{e \log(n)}\right)}^{n}
b29b24
Bnp(n)B_{n} \ge p(n)

Divisibility properties

Touchard's congruence

60740b
Bp2(modp)B_{p} \equiv 2 \pmod {p}
dd9d26
Bn+pBn+Bn+1(modp)B_{n + p} \equiv B_{n} + B_{n + 1} \pmod {p}
b41c49
Bn+pmmBn+Bn+1(modp)B_{n + {p}^{m}} \equiv m B_{n} + B_{n + 1} \pmod {p}

Periodicity

050ee1
Bn{0,n2(mod3)1,otherwise(mod2)B_{n} \equiv \begin{cases} 0, & n \equiv 2 \pmod {3}\\1, & \text{otherwise}\\ \end{cases} \pmod {2}
a4d6fc
Bn+aBn(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+aBn(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}        BnPn \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,0)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, 0\right)}
dc6806
det ⁣((B0+0B0+1B0+nB1+0B1+1B1+nBn+0Bn+1Bn+n))=k=1nk!=G ⁣(n+2)\operatorname{det}\!\left(\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}}\right) = \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.

2019-10-05 13:11:19.856591 UTC