# Ordered Bell number

Short description: Number of weak orderings The 13 possible strict weak orderings on a set of three elements {a, b, c}

In number theory and enumerative combinatorics, the ordered Bell numbers or Fubini numbers count the number of weak orderings on a set of n elements (orderings of the elements into a sequence allowing ties, such as might arise as the outcome of a horse race). Starting from n = 0, these numbers are

1, 1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563, ... (sequence A000670 in the OEIS).

The ordered Bell numbers may be computed via a summation formula involving binomial coefficients, or by using a recurrence relation. Along with the weak orderings, they count several other types of combinatorial objects that have a bijective correspondence to the weak orderings, such as the ordered multiplicative partitions of a squarefree number or the faces of all dimensions of a permutohedron (e.g. the sum of faces of all dimensions in the truncated octahedron is 1 + 14 + 36 + 24 = 75).

## History 13 plane trees with ordered leaves and equal-length root-leaf paths, with the gaps between adjacent leaves labeled by the height above the leaves of the nearest common ancestor. These labels induce a weak ordering on the gaps, showing that the trees of this type are counted by the ordered Bell numbers.

The ordered Bell numbers appear in the work of (Cayley 1859), who used them to count certain plane trees with n + 1 totally ordered leaves. In the trees considered by Cayley, each root-to-leaf path has the same length, and the number of nodes at distance i from the root must be strictly smaller than the number of nodes at distance i + 1, until reaching the leaves. In such a tree, there are n pairs of adjacent leaves, that may be weakly ordered by the height of their lowest common ancestor; this weak ordering determines the tree. (Mor Fraenkel) call the trees of this type "Cayley trees", and they call the sequences that may be used to label their gaps (sequences of n positive integers that include at least one copy of each positive integer between one and the maximum value in the sequence) "Cayley permutations".

(Pippenger 2010) traces the problem of counting weak orderings, which has the same sequence as its solution, to the work of (Whitworth 1886).

These numbers were called Fubini numbers by Louis Comtet, because they count the number of different ways to rearrange the ordering of sums or integrals in Fubini's theorem, which in turn is named after Guido Fubini. For instance, for a bivariate integral, Fubini's theorem states that

$\displaystyle{ \int_A\left(\int_B f(x,y)\,\text{d}y\right)\,\text{d}x=\int_B\left(\int_A f(x,y)\,\text{d}x\right)\,\text{d}y=\int_{A\times B} f(x,y)\,\text{d}(x,y), }$

where these three formulations correspond to the three weak orderings on two elements. In general, in a multivariate integral, the ordering in which the variables may be grouped into a sequence of nested integrals forms a weak ordering.

The Bell numbers, named after Eric Temple Bell, count the number of partitions of a set, and the weak orderings that are counted by the ordered Bell numbers may be interpreted as a partition together with a total order on the sets in the partition.

## Formula

The nth 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 n-element set into k nonempty subsets, 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:

$\displaystyle{ a(n)= \sum_{k=0}^n k! \left\{\begin{matrix} n \\ k \end{matrix}\right\}=\sum_{k=0}^n \sum_{j=0}^k (-1)^{k-j} \binom{k}{j}j^n=\frac12\sum_{m=0}^\infty\frac{m^n}{2^{m}}. }$

An alternative summation formula expresses the ordered Bell numbers in terms of the Eulerian numbers, which count the number of permutations of n items with k + 1 runs of increasing items:

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

where An is the nth Eulerian polynomial.

The exponential generating function of the ordered Bell numbers is

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

This can be expressed equivalently as the fact that the ordered Bell numbers are the numbers in the first column of the infinite matrix (2I − P)−1, where I is the identity matrix and P is an infinite matrix form of Pascal's triangle. Based on a contour integration of this generating function, the ordered Bell numbers can be expressed by the infinite sum

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

and approximated as

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

Because log 2 is less than one, the form of this approximation shows that the ordered Bell numbers exceed the corresponding factorials by an exponential factor. The asymptotic convergence of this approximation may be expressed as

$\displaystyle{ \lim_{n\to\infty} \frac{n\,a(n-1)}{a(n)}=\log 2. }$

## Recurrence and modular periodicity

As well as the formulae above, the ordered Bell numbers may be calculated by the recurrence relation

$\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 n items may be broken down into a choice of some nonempty set of i items that go into the first equivalence class of the ordering, together with a smaller weak ordering on the remaining n − i items. As a base case for the recurrence, 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 n,

$\displaystyle{ a(n+4) \equiv a(n) \pmod{10}, }$
$\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}. }$

Several additional modular identities are given by (Good 1975) and (Poonen 1988).