Summation

The ${\displaystyle n}$th ordered Bell number may be given by a summation formula involving the Stirling numbers of the second kind, which count the number of partitions of an ${\displaystyle n}$-element set into ${\displaystyle k}$ nonempty subsets. A weak ordering may be described as a permutation of the subsets in this partition, and so the ordered Bell numbers (the number of weak orderings) may be calculated by summing these numbers, multiplied by a factorial, ${\displaystyle k!}$, that counts the number of these permutations: ^[11][12]

$${\displaystyle a(n)=\sum _{k=0}^{n}k!\left\{{\begin{matrix}n\\k\end{matrix}}\right\}}$$

An alternative interpretation of the terms of this sum is that they count the features of each dimension in a permutohedron of dimension ${\displaystyle n}$, with the ${\displaystyle k}$th term counting the features of dimension ${\displaystyle n-k}$. For instance, the three-dimensional permutohedron, the truncated octahedron, has one volume (${\displaystyle k=0}$), 14 two-dimensional faces (${\displaystyle k=1}$), 36 edges (${\displaystyle k=2}$), and 24 vertices (${\displaystyle k=3}$). The total number of these faces is 1 + 14 + 36 + 24 = 75, an ordered Bell number, corresponding to the summation formula above for ${\displaystyle n=3}$.^[13]

The same summation may be expanded out into a double summation involving binomial coefficients (using a formula expressing Stirling numbers as a sum of binomial coefficients), or given by an infinite series:^[7][10]

$${\displaystyle a(n)=\sum _{k=0}^{n}\sum _{j=0}^{k}(-1)^{k-j}{\binom {k}{j}}j^{n}={\frac {1}{2}}\sum _{m=0}^{\infty }{\frac {m^{n}}{2^{m}}}.}$$

Another summation formula expresses the ordered Bell numbers in terms of the Eulerian numbers, which count the number of permutations of ${\displaystyle n}$ items with ${\displaystyle k+1}$ runs of increasing items:^[14]

$${\displaystyle a(n)=\sum _{k=0}^{n-1}2^{k}\left\langle {\begin{matrix}n\\k\end{matrix}}\right\rangle =A_{n}(2),}$$

where ${\displaystyle A_{n}}$ is the ${\displaystyle n}$th Eulerian polynomial.^[14]

Generating function and approximation

The exponential generating function of the ordered Bell numbers is^{[7][10][12][15]}

$${\displaystyle \sum _{n=0}^{\infty }a(n){\frac {x^{n}}{n!}}={\frac {1}{1-(e^{x}-1)}}={\frac {1}{2-e^{x}}}.}$$

The form of this function corresponds to the fact that the ordered Bell numbers are the numbers in the first column of the infinite matrix ${\displaystyle (2I-P)^{-1}}$, where ${\displaystyle I}$ is the identity matrix and ${\displaystyle P}$ is an infinite matrix form of Pascal's triangle.^[16] Based on a contour integration of this generating function, the ordered Bell numbers can be expressed by the infinite sum^[3][17]

$${\displaystyle a(n)={\frac {n!}{2}}\sum _{k=-\infty }^{\infty }(\log 2+2\pi ik)^{-(n+1)},\qquad n\geq 1,}$$

and approximated (by keeping only the ${\displaystyle k=0}$ term of the sum) as^{[3][12][18][19][17]}

$${\displaystyle a(n)\approx {\frac {n!}{2(\log 2)^{n+1}}}.}$$

Recurrence and modular periodicity

As well as the formulae above, the ordered Bell numbers may be calculated by the recurrence relation^[7][18]

${\displaystyle a(n)=\sum _{i=1}^{n}{\binom {n}{i}}a(n-i).}$

The intuitive meaning of this formula is that a weak ordering on ${\displaystyle n}$ items may be broken down into a choice of some nonempty set of ${\displaystyle i}$ items that go into the first equivalence class of the ordering, together with a smaller weak ordering on the remaining ${\displaystyle n-i}$ items. As a base case for the recurrence, ${\displaystyle a(0)=1}$ (there is one weak ordering on zero items). Based on this recurrence, these numbers can be shown to obey certain periodic patterns in modular arithmetic: for sufficiently large ${\displaystyle n}$,

${\displaystyle a(n+4)\equiv a(n){\pmod {10}},}$^[18]

${\displaystyle a(n+20)\equiv a(n){\pmod {100}},}$

${\displaystyle a(n+100)\equiv a(n){\pmod {1000}},}$ and

${\displaystyle a(n+500)\equiv a(n){\pmod {10000}}.}$^[20]

Several additional modular identities are given by Good (1975) and Poonen (1988).^[11][21]