Weak orderings arrange their elements into a sequence allowing
ties. This possibility describes various real-world scenarios, including certain sporting contests such as
horse races.[1][2] A weak ordering can be formalized axiomatically by a
partially ordered set for which
incomparability is an
equivalence relation. The
equivalence classes of this relation partition the elements of the ordering into subsets of mutually tied elements, and these equivalence classes can then be linearly ordered by the weak ordering. Thus, a weak ordering can be described as an
ordered partition, a partition of its elements, together with a
linear order on the sets of the partition.[5] For instance, the ordered partition {a,b},{c},{d,e,f} describes an ordered partition on six elements in which a and b are tied and both less than the other four elements, and c is less than d, e, and f, which are all tied with each other.
The th ordered Bell number, denoted here , gives the number of distinct weak orderings on elements.[6] For instance, there are three weak orderings on the two elements a and b: they can be ordered with a before b, with b before a, or with both tied. The figure shows the 13 weak orderings on three elements.
Starting from , the ordered Bell numbers are
1, 1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563, ... (sequence A000670 in the
OEIS).
History
The ordered Bell numbers appear in the work of
Cayley (1859), who used them to count certain
plane trees with 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 from the root must be strictly smaller than the number of nodes at distance , until reaching the leaves.[7] In such a tree, there are 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 (1984) call the trees of this type "Cayley trees", and they call the sequences that may be used to label their gaps (sequences of positive integers that include at least one copy of each positive integer between one and the maximum value in the sequence) "Cayley permutations".[8]
Pippenger (2010) traces the problem of counting weak orderings, which has the same sequence as its solution, to the work of
Whitworth (1886).[9][10] 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.[11] 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.[12]
The equivalence between counting Cayley trees and counting weak orderings was observed in 1970 by
Donald Knuth, using an early form of the
On-Line Encyclopedia of Integer Sequences (OEIS). This became one of the first successful uses of the OEIS to discover equivalences between different counting problems.[13]
Formulas
Summation
Because weak orderings can be described as linear orderings on the subsets of a partition, one can count weak orderings by counting linear orderings and partitions, and combining the results appropriately. The
Stirling numbers of the second kind, denoted , count the number of partitions of an -element set into nonempty subsets. A weak ordering may be obtained from such a partition by choosing one of linear orderings of its subsets. Therefore, the ordered Bell numbers can be counted by summing over the possible numbers of subsets in a partition (the parameter ) and, for each value of , multiplying the number of partitions by the number of linear orderings . That is, as a
summation formula:[14][15]
An alternative interpretation of the terms of this sum is that they count the features of each dimension in a
permutohedron of dimension , with the th term counting the features of dimension . For instance, the three-dimensional permutohedron, the
truncated octahedron,
has one volume (), 14 two-dimensional faces (), 36 edges (), and 24 vertices (). The total number of these faces is 1 + 14 + 36 + 24 = 75, an ordered Bell number, corresponding to the summation formula above for .[16] By general results on summations involving Stirling numbers, it follows that the ordered Bell numbers are
log-convex, meaning that they obey the inequality for all .[17]
By expanding each Stirling number in this formula into a sum of
binomial coefficients, the formula for the ordered Bell numbers may be expanded out into a double summation. The ordered Bell numbers may also be given by an
infinite series:[9][12]
Another summation formula expresses the ordered Bell numbers in terms of the
Eulerian numbers, which count the number of permutations of items in which items are less than the next item:[18]
As with many other integer sequences, reinterpreting the sequence as the coefficients of a
power series and working with the function that results from summing this series can provide useful information about the sequence. For sequences with faster than exponential growth, such as the ordered Bell numbers, the
ordinary generating function may not converge, so instead the
exponential generating function is used. For the ordered Bell numbers, it is:[9][12][15][19]
Here, the left hand side is just the definition of the exponential generating function and the right hand side is the function obtained from this summation.
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. Here is the
identity matrix and is an infinite matrix form of
Pascal's triangle. Each row of 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[3][21]
Here, stands for the
natural logarithm, whose base is . This leads to an approximation for the ordered Bell numbers, obtained by using only the first term of this sum and discarding the remaining terms:[3][15][22][23][21]
Thus, the ordered Bell numbers are larger than the factorials by an exponential factor, whose base is approximately . Here, as in
Stirling's approximation to the factorial, the indicates that the ratio between the ordered Bell numbers and their approximation tends to one in the limit as grows arbitrarily large. As expressed in
little o notation, this ratio is , and the error term is exponentially small in .[3]
Recurrence and modular periodicity
As well as the formulae above, the ordered Bell numbers may be calculated by the
recurrence relation[9][22]
The intuitive meaning of this formula is that a weak ordering on items may be broken down into a choice of some nonempty set of items that go into the first equivalence class of the ordering, together with a smaller weak ordering on the remaining items. As a base case for the recurrence, (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 ,
As has already been mentioned, the ordered Bell numbers count weak orderings,
permutohedron faces, Cayley trees, Cayley permutations, ordered multiplicative partitions of squarefree numbers, and equivalent formulae in Fubini's theorem. Weak orderings in turn have many other applications. 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. For this reason, the ordered Bell numbers count the possible number of outcomes of a horse race.[1] In contrast, when items are ordered or ranked in a way that does not allow ties (such as occurs with the ordering of cards in a deck of cards, or batting orders among
baseball players), the number of orderings for items is a
factorial number,[26] which is significantly smaller than the corresponding ordered Bell number.[27]
Velleman & Call (1995) consider
combination locks with a numeric keypad, in which several keys may be pressed simultaneously and a combination consists of a sequence of keypresses that includes each key exactly once. As they show, the number of different combinations in such a system is given by the ordered Bell numbers.[18]
A
parking function, in mathematics, is a finite sequence of positive integers with the property that, for every up to the sequence length, the sequence contains at least values that are at most . A sequence of this type, of length , describes the following process: a sequence of cars arrives on a street with parking spots. Each car has a preferred parking spot, given by its value in the sequence. When a car arrives on the street, it parks in its preferred spot, or, if that is full, in the next available spot. A sequence of preferences forms a parking function if and only if each car can find a parking spot on or after its preferred spot. The number of parking functions of length is exactly . For a restricted class of parking functions, in which each car parks either on its preferred spot or on the next spot, the number of parking functions is given by the ordered Bell numbers. Each restricted parking function corresponds to a weak ordering in which the cars that get their preferred spot are ordered by these spots, and each remaining car is tied with the car in its preferred spot. The
permutations, counted by the factorials, are parking functions for which each car parks on its preferred spot.[28] This application also provides a
combinatorial proof for
upper and lower bounds on the ordered Bell numbers of a simple form,
Kemeny (1956) uses the ordered Bell numbers to analyze
n-ary relations, mathematical statements that might be true of some choices of the arguments to the relation and false for others. By the "complexity" of a relation he means the number of other relations one can derive from the given one by permuting and repeating its arguments. For instance, for , a relation on two arguments and might take the form . By Kemeny's analysis, it has derived relations. These are the given relation , the
converse relation obtained by swapping the arguments, and the
unary relation obtained by repeating an argument. (Repeating the other argument produces the same relation.)[29]
Ellison & Klein (2001) point out an application of these numbers to
optimality theory in
linguistics. 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.[27]
References
^
abcde Koninck, J. M. (2009),
Those Fascinating Numbers, American Mathematical Society, p. 4,
ISBN9780821886311. Because of this application, de Koninck calls these numbers "horse numbers", but this name does not appear to be in widespread use.
^
abEllison, T. Mark; Klein, Ewan (2001), "Review: The Best of All Possible Words (review of Optimality Theory: An Overview, Archangeli, Diana & Langendoen, D. Terence, eds., Blackwell, 1997)", Journal of Linguistics, 37 (1): 127–143,
JSTOR4176645
^Meyles, Lucas Chaves;
Harris, Pamela E.; Jordaan, Richter; Kirby, Gordon Rojas; Sehayek, Sam; Spingarn, Ethan (2023), Unit-interval parking functions and the permutohedron,
arXiv:2305.15554; Meyles et al credit the connection between parking functions and ordered Bell numbers to a 2021 bachelor's thesis by Kimberly P. Hadaway of Williams College