In number theory and enumerative combinatorics, the ordered Bell numbers or Fubini numbers count the weak orderings on a set of n {\displaystyle n} 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 n {\displaystyle n} th ordered Bell number, denoted here a ( n ) {\displaystyle a(n)} , gives the number of distinct weak orderings on n {\displaystyle n} 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 n = 0 {\displaystyle n=0} , the ordered Bell numbers a ( n ) {\displaystyle a(n)} are
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 n {\displaystyle n} 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 n {\displaystyle n} is exactly 2 n − 1 {\displaystyle 2^{n-1}} . This is because a composition is determined by its set of partial sums, which may be any subset of the integers from 1 to n − 1 {\displaystyle n-1} .
History
The ordered Bell numbers appear in the work of Cayley (1859), who used them to count certain plane trees with n + 1 {\displaystyle 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 {\displaystyle i} from the root must be strictly smaller than the number of nodes at distance i + 1 {\displaystyle i+1} , until reaching the leaves. In such a tree, there are n {\displaystyle 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 (1984) call the trees of this type "Cayley trees", and they call the sequences that may be used to label their gaps (sequences of n {\displaystyle 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 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
… excerpt ends here. Continue reading the full article.
