# Bell numbers

## Definitions

Symbol: BellNumber $B_{n}$ Bell number
$B_{n} = \text{A000110}\!\left(n\right)$

## Domain and codomain

$n \in \mathbb{Z}_{\ge 0} \;\implies\; B_{n} \in \mathbb{Z}_{\ge 1}$

## Specific values

### First cases as set partitions

$B_{0} = \# \left\{\left\{\left\{\right\}\right\}\right\} = 1$
$B_{1} = \# \left\{\left\{\left\{1\right\}\right\}\right\} = 1$
$B_{2} = \# \left\{\left\{\left\{1\right\}, \left\{2\right\}\right\}, \left\{\left\{1, 2\right\}\right\}\right\} = 2$
$B_{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

Table of $B_{n}$ for $0 \le n \le 40$
Table of $B_{{10}^{n}}$ to 50 digits for $0 \le n \le 20$

## Infinite series representations

$B_{n} = \frac{1}{e} \sum_{k=0}^{\infty} \frac{{k}^{n}}{k !}$

## Sum representations

$B_{n} = \sum_{k=0}^{n} \left\{{n \atop k}\right\}$
$B_{n} = \sum_{k=1}^{n} \frac{{k}^{n}}{k !} \sum_{j=0}^{n - k} \frac{{\left(-1\right)}^{j}}{j !}$
$B_{n + 1} = \sum_{k=0}^{n} {n \choose k} B_{k}$

## Generating functions

$\sum_{n=0}^{\infty} B_{n} {x}^{n} = \sum_{k=0}^{\infty} \frac{{x}^{k}}{\prod_{j=1}^{k} \left(1 - j x\right)}$
$\sum_{n=0}^{\infty} \frac{B_{n}}{n !} {x}^{n} = \exp\!\left({e}^{x} - 1\right)$

## Integral representations

$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)$
$B_{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

$\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$
$B_{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

$B_{n + 1} \ge B_{n}$
$B_{n + 1} > B_{n}$
$B_{n + 1} < n B_{n}$
$B_{n + 1} \ge 2 B_{n}$
$B_{n}^{2} \le B_{n - 1} B_{n + 1} \le \left(1 + \frac{1}{n}\right) B_{n}^{2}$
$B_{n} B_{m} \le B_{n + m} \le {n + m \choose n} B_{n} B_{m}$

### Upper bounds

$B_{n} \le n !$
$B_{n} \le {\left(\frac{0.792 n}{\log\!\left(n + 1\right)}\right)}^{n}$

### Lower bounds

$B_{n} \ge {e}^{n - 2}$
$B_{n} \ge {k}^{n - k}$
$B_{n} \ge {\left(\frac{n}{e \log(n)}\right)}^{n}$
$B_{n} \ge p(n)$

## Divisibility properties

### Touchard's congruence

$B_{p} \equiv 2 \pmod {p}$
$B_{n + p} \equiv B_{n} + B_{n + 1} \pmod {p}$
$B_{n + {p}^{m}} \equiv m B_{n} + B_{n + 1} \pmod {p}$

### Periodicity

$B_{n} \equiv \begin{cases} 0, & n \equiv 2 \pmod {3}\\1, & \text{otherwise}\\ \end{cases} \pmod {2}$
$B_{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}$
$B_{n + a} \equiv B_{n} \pmod {m}\; \text{ where } a = \text{A054767}\!\left(m\right)$

### Prime values

$n \in \left\{2, 3, 7, 13, 42, 55, 2841\right\} \;\implies\; B_{n} \in \mathbb{P}$

## Matrix fomulas

$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)}$
$\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.

2020-08-27 09:56:25.682319 UTC