Ordered Bell number

Weak orderings arrange their elements into a sequence allowing ties, such as might arise as the outcome of a horse race.

[1][2] The ordered Bell numbers were studied in the 19th century by Arthur Cayley and William Allen Whitworth.

[4] These numbers may be computed via a summation formula involving binomial coefficients, or by using a recurrence relation.

This possibility describes various real-world scenarios, including certain sporting contests such as horse races.

For instance, the ordered partition {a,b},{c},{d,e,f} discussed above corresponds in this way to the composition 2 + 1 + 3.

[4] The ordered Bell numbers appear in the work of Cayley (1859), who used them to count certain plane trees with

In the trees considered by Cayley, each root-to-leaf path has the same length, and the number of nodes at distance

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

One way to explain this summation formula involves a mapping from weak orderings on the numbers from 1 to

starts with the numbers in the same row of Pascal's triangle, and then continues with an infinite repeating sequence of zeros.

[20] Based on a contour integration of this generating function, the ordered Bell numbers can be expressed by the infinite sum[21][5]

This leads to an approximation for the ordered Bell numbers, obtained by using only the term for

Multiplying these two factors, and then summing over the choices of how many elements to include in the first set, gives the number of weak orderings,

Based on this recurrence, these numbers can be shown to obey certain periodic patterns in modular arithmetic: for sufficiently large

[14][25][26] Peter Bala has conjectured that this sequence is eventually periodic (after a finite number of terms) modulo each positive integer

[4] As has already been mentioned, the ordered Bell numbers count weak orderings, permutohedron faces, Cayley trees, Cayley permutations, and equivalent formulae in Fubini's theorem.

For instance, in horse racing, photo finishes have eliminated most but not all ties, called in this context dead heats, and the outcome of a race that may contain ties (including all the horses, not just the first three finishers) may be described using a weak ordering.

, an ordered multiplicative partition is a product of powers of the same prime number, with exponents summing to

[31] A parking function, in mathematics, is a finite sequence of positive integers with the property that, for every

[32] This application also provides a combinatorial proof for upper and lower bounds on the ordered Bell numbers of a simple form,

Here, a Coxeter group can be thought of as a finite system of reflection symmetries, closed under repeated reflections, whose mirrors partition a Euclidean space into the cells of the Coxeter complex.

[4] Kemeny (1956) uses the ordered Bell numbers to analyze n-ary relations, mathematical statements that might be true of some choices of the

In this theory, grammars for natural languages are constructed by ranking certain constraints, and (in a phenomenon called factorial typology) the number of different grammars that can be formed in this way is limited to the number of permutations of the constraints.

A paper reviewed by Ellison and Klein suggested an extension of this linguistic model in which ties between constraints are allowed, so that the ranking of constraints becomes a weak order rather than a total order.

As they point out, the much larger magnitude of the ordered Bell numbers, relative to the corresponding factorials, allows this theory to generate a much richer set of grammars.

[4] Although the ordinary generating function of the ordered Bell numbers fails to converge, it describes a power series that (evaluated at

Truncating this series to a bounded number of terms and then applying the result for unbounded values of

[8] In the algebra of noncommutative rings, an analogous construction to the (commutative) quasisymmetric functions produces a graded algebra WQSym whose dimensions in each grade are given by the ordered Bell numbers.

This recurrence differs from the one given earlier for the ordered Bell numbers, in two respects: omitting the

These differences have offsetting effects, and the resulting weights are the ordered Bell numbers.

The 13 possible strict weak orderings on a set of three elements { a , b , c }
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.
A three-dimensional truncated octahedron , with its vertices labeled by their four-dimensional coordinates as a permutohedron
The Coxeter complex for cuts space into 24 triangular cones, shown here by their intersections with a unit sphere . The reflection planes of cut the sphere in great circles . The faces of the complex intersect the sphere in 24 triangles, 36 arcs, and 14 vertices; one more face, at the center of the sphere, is not visible.