Number of weak orderings
In number theory and enumerative combinatorics, the ordered Bell numbers or Fubini numbers count the weak orderings on a set of formula_1 elements. Weak orderings arrange their elements into a sequence allowing ties, such as might arise as the outcome of a horse race.
The ordered Bell numbers were studied in the 19th century by Arthur Cayley and William Allen Whitworth. They are named after Eric Temple Bell, who wrote about the Bell numbers, which count the partitions of a set; the ordered Bell numbers count partitions that have been equipped with a total order. Their alternative name, the Fubini numbers, comes from a connection to Guido Fubini and Fubini's theorem on equivalent forms of multiple integrals. Because weak orderings have many names, ordered Bell numbers may also be called by those names, for instance as the numbers of preferential arrangements or the numbers of asymmetric generalized weak orders.
These numbers may be computed via a summation formula involving binomial coefficients, or by using a recurrence relation. They also count 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.
Definitions and examples.
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. 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 and a total order on the sets of the partition. 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 formula_1th ordered Bell number, denoted here formula_3, gives the number of distinct weak orderings on formula_1 elements. 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 formula_5, the ordered Bell numbers formula_3 are
 ;templatestyles src="Block indent/styles.css"/ ;
When the elements to be ordered are unlabeled (only the number of elements in each tied set matters, not their identities) what remains is a composition or ordered integer partition, a representation of formula_1 as an ordered sum of positive integers. For instance, the ordered partition {"a","b"},{"c"},{"d","e","f"} discussed above corresponds in this way to the composition 2 + 1 + 3. The number of compositions of formula_1 is exactly formula_9. This is because a composition is determined by its set of partial sums, which may be any subset of the integers from 1 to formula_10.
History.
The ordered Bell numbers appear in the work of , who used them to count certain plane trees with formula_11 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 formula_12 from the root must be strictly smaller than the number of nodes at distance formula_13, until reaching the leaves. In such a tree, there are formula_1 pairs of adjacent leaves, that may be weakly ordered by the height of their lowest common ancestor; this weak ordering determines the tree. call the trees of this type "Cayley trees", and they call the sequences that may be used to label their gaps (sequences of formula_1 positive integers that include at least one copy of each positive integer between one and the maximum value in the sequence) "Cayley permutations".
 traces the problem of counting weak orderings, which has the same sequence as its solution, to the work of . These numbers were called Fubini numbers by Louis Comtet, because they count the different ways to rearrange the ordering of sums or integrals in Fubini's theorem, which in turn is named after Guido Fubini. The Bell numbers, named after Eric Temple Bell, count the 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.
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.
Formulas.
Summation.
Because weak orderings can be described as total orderings on the subsets of a partition, one can count weak orderings by counting total orderings and partitions, and combining the results appropriately. The Stirling numbers of the second kind, denoted formula_16, count the partitions of an formula_1-element set into formula_18 nonempty subsets. A weak ordering may be obtained from such a partition by choosing one of formula_19 total 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 formula_18) and, for each value of formula_18, multiplying the number of partitions formula_16 by the number of total orderings formula_19. That is, as a summation formula:
formula_24
By general results on summations involving Stirling numbers, it follows that the ordered Bell numbers are log-convex, meaning that they obey the inequality formula_25 for all formula_26.
An alternative interpretation of the terms of this sum is that they count the features of each dimension in a permutohedron of dimension formula_1, with the formula_18th term counting the features of dimension formula_29. A permutohedron is a convex polytope, the convex hull of points whose coordinate vectors are the permutations of the numbers from 1 to formula_1. These vectors are defined in a space of dimension formula_11, but they and their convex hull all lie in an formula_1-dimensional affine subspace. For instance, the three-dimensional permutohedron is the truncated octahedron, the convex hull of points whose coordinates are permutations of (1,2,3,4), in the three-dimensional subspace of points whose coordinate sum is 10. This polyhedron has one volume (formula_33), 14 two-dimensional faces (formula_34), 36 edges (formula_35), and 24 vertices (formula_36). The total number of these faces is 1 + 14 + 36 + 24 = 75, an ordered Bell number, corresponding to the summation formula above for formula_37.
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:
formula_38
Another summation formula expresses the ordered Bell numbers in terms of the Eulerian numbers formula_39, which count the permutations of formula_1 items in which formula_18 pairs of consecutive items are in increasing order:
formula_42
where formula_43 is the formula_1th Eulerian polynomial. One way to explain this summation formula involves a mapping from weak orderings on the numbers from 1 to formula_1 to permutations, obtained by sorting each tied set into numerical order. Under this mapping, each permutation with formula_18 consecutive increasing pairs comes from formula_47 weak orderings, distinguished from each other by the subset of the consecutive increasing pairs that are tied in the weak ordering.
Generating function and approximation.
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. 
The fast growth of the ordered Bell numbers causes their ordinary generating function to diverge; instead the exponential generating function is used. For the ordered Bell numbers, it is:
formula_48
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 formula_49. Here formula_50 is the identity matrix and formula_51 is an infinite matrix form of Pascal's triangle. Each row of formula_51 starts with the numbers in the same row of Pascal's triangle, and then continues with an infinite repeating sequence of zeros.
Based on a contour integration of this generating function, the ordered Bell numbers can be expressed by the infinite sum
formula_53
Here, formula_54 stands for the natural logarithm. This leads to an approximation for the ordered Bell numbers, obtained by using only the term for formula_33 in this sum and discarding the remaining terms:
formula_56
where formula_57. Thus, the ordered Bell numbers are larger than the factorials by an exponential factor. Here, as in Stirling's approximation to the factorial, the formula_58 indicates asymptotic equivalence. That is, the ratio between the ordered Bell numbers and their approximation tends to one in the limit as formula_1 grows arbitrarily large. As expressed in little o notation, the relative error is formula_60, and the formula_61 error term decays exponentially as formula_1 grows.
Comparing the approximations for formula_63 and formula_3 shows that
formula_65
For example, taking formula_66 gives the approximation formula_67 to formula_68.
This sequence of approximations, and this example from it, were calculated by Ramanujan, using a general method for solving equations numerically (here, the equation formula_69).
Recurrence and modular periodicity.
As well as the formulae above, the ordered Bell numbers may be calculated by the recurrence relation
formula_70
The intuitive meaning of this formula is that a weak ordering on formula_1 items may be broken down into a choice of some nonempty set of formula_12 items that go into the first equivalence class of the ordering, together with a smaller weak ordering on the remaining formula_73 items. There are formula_74 choices of the first set, and formula_75 choices of the weak ordering on the rest of the elements. 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, formula_3. As a base case for the recurrence, formula_77 (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 formula_1,
 ;templatestyles src="Block indent/styles.css"/ ;formula_79
 ;templatestyles src="Block indent/styles.css"/ ;formula_80
 ;templatestyles src="Block indent/styles.css"/ ;formula_81 and
 ;templatestyles src="Block indent/styles.css"/ ;formula_82
Many more modular identities are known, including identities modulo any prime power. Peter Bala has conjectured that this sequence is eventually periodic (after a finite number of terms) modulo each positive integer formula_18, with a period that divides Euler's totient function of formula_18, the number of residues mod formula_18 that are relatively prime to formula_18.
Applications.
Combinatorial enumeration.
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. 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. 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 formula_1 items is a factorial number formula_88, which is significantly smaller than the corresponding ordered Bell number.
Problems in many areas can be formulated using weak orderings, with solutions counted using ordered Bell numbers. 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. In "seru", a Japanese technique for balancing assembly lines, cross-trained workers are allocated to groups of workers at different stages of a production line. The number of alternative assignments for a given number of workers, taking into account the choices of how many stages to use and how to assign workers to each stage,