Ordered Bell number

From HandWiki
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 [math]\displaystyle{ n }[/math] elements. Weak orderings arrange their elements into a sequence allowing ties, such as might arise as the outcome of a horse race).[1][2] Starting from [math]\displaystyle{ n=0 }[/math], 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[3] or the faces of all dimensions of a permutohedron.[4]


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 [math]\displaystyle{ n+1 }[/math] 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 [math]\displaystyle{ i }[/math] from the root must be strictly smaller than the number of nodes at distance [math]\displaystyle{ i+1 }[/math], until reaching the leaves.[5] In such a tree, there are [math]\displaystyle{ n }[/math] 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 [math]\displaystyle{ n }[/math] positive integers that include at least one copy of each positive integer between one and the maximum value in the sequence) "Cayley permutations".[6]

(Pippenger 2010) traces the problem of counting weak orderings, which has the same sequence as its solution, to the work of (Whitworth 1886).[7][8] 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.[9] 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.[10]



The [math]\displaystyle{ n }[/math]th 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 [math]\displaystyle{ n }[/math]-element set into [math]\displaystyle{ k }[/math] nonempty subsets. A weak ordering may be described as a permutation of the subsets in this partition, and so the ordered Bell numbers (the number of weak orderings) may be calculated by summing these numbers, multiplied by a factorial, [math]\displaystyle{ k! }[/math], that counts the number of these permutations: [11][12] [math]\displaystyle{ a(n) = \sum_{k=0}^n k! \left\{\begin{matrix} n \\ k \end{matrix}\right\} }[/math] An alternative interpretation of the terms of this sum is that they count the features of each dimension in a permutohedron of dimension [math]\displaystyle{ n }[/math], with the [math]\displaystyle{ k }[/math]th term counting the features of dimension [math]\displaystyle{ n-k }[/math]. For instance, the three-dimensional permutohedron, the truncated octahedron, has one volume ([math]\displaystyle{ k=0 }[/math]), 14 two-dimensional faces ([math]\displaystyle{ k=1 }[/math]), 36 edges ([math]\displaystyle{ k=2 }[/math]), and 24 vertices ([math]\displaystyle{ k=3 }[/math]). The total number of these faces is 1 + 14 + 36 + 24 = 75, an ordered Bell number, corresponding to the summation formula above for [math]\displaystyle{ n=3 }[/math].[13]

The same summation may be 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:[7][10] [math]\displaystyle{ a(n) = \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}}. }[/math]

Another summation formula expresses the ordered Bell numbers in terms of the Eulerian numbers, which count the number of permutations of [math]\displaystyle{ n }[/math] items with [math]\displaystyle{ k+1 }[/math] runs of increasing items:[14] [math]\displaystyle{ a(n)=\sum_{k=0}^{n-1} 2^k \left\langle\begin{matrix} n \\ k \end{matrix}\right\rangle=A_n(2), }[/math] where [math]\displaystyle{ A_n }[/math] is the [math]\displaystyle{ n }[/math]th Eulerian polynomial.[14]

Generating function and approximation

The exponential generating function of the ordered Bell numbers is[7][10][12][15] [math]\displaystyle{ \sum_{n=0}^\infty a(n)\frac{x^n}{n!} = \frac{1}{1-(e^x-1)} = \frac{1}{2-e^x}. }[/math] 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 [math]\displaystyle{ (2I-P)^{-1} }[/math], where [math]\displaystyle{ I }[/math] is the identity matrix and [math]\displaystyle{ P }[/math] is an infinite matrix form of Pascal's triangle.[16] Based on a contour integration of this generating function, the ordered Bell numbers can be expressed by the infinite sum[3][17] [math]\displaystyle{ a(n)=\frac{n!}{2}\sum_{k=-\infty}^{\infty}(\log 2+2\pi ik)^{-(n+1)},\qquad n\ge1, }[/math] and approximated (by keeping only the [math]\displaystyle{ k=0 }[/math] term of the sum) as[3][12][18][19][17] [math]\displaystyle{ a(n)\approx \frac{n!}{2(\log 2)^{n+1}}. }[/math]

Recurrence and modular periodicity

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

[math]\displaystyle{ a(n) = \sum_{i=1}^{n}\binom{n}{i}a(n-i). }[/math]

The intuitive meaning of this formula is that a weak ordering on [math]\displaystyle{ n }[/math] items may be broken down into a choice of some nonempty set of [math]\displaystyle{ i }[/math] items that go into the first equivalence class of the ordering, together with a smaller weak ordering on the remaining [math]\displaystyle{ n-i }[/math] items. As a base case for the recurrence, [math]\displaystyle{ a(0)=1 }[/math] (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 [math]\displaystyle{ n }[/math],

[math]\displaystyle{ a(n+4) \equiv a(n) \pmod{10}, }[/math][18]
[math]\displaystyle{ a(n+20) \equiv a(n) \pmod{100}, }[/math]
[math]\displaystyle{ a(n+100) \equiv a(n) \pmod{1000}, }[/math] and
[math]\displaystyle{ a(n+500) \equiv a(n) \pmod{10000}. }[/math][20]

Several additional modular identities are given by (Good 1975) and (Poonen 1988).[11][21]

Additional applications

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] or the possible outcomes of a multi-candidate election.[22] 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 [math]\displaystyle{ n }[/math] items is a factorial number [math]\displaystyle{ n! }[/math],[23] which is significantly smaller than the corresponding ordered Bell number.[24]

(Kemeny 1956) uses the ordered Bell numbers to describe the "complexity" of an n-ary relation, by which he means the number of other relations one can form from it by permuting and repeating its arguments (lowering the arity with every repetition). In this application, for each derived relation, the arguments of the original relation are weakly ordered by the positions of the corresponding arguments of the derived relation.[25]

(Velleman Call) 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.[14]

(Ellison Klein) 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.[24]


  1. 1.0 1.1 de Koninck, J. M. (2009), Those Fascinating Numbers, American Mathematical Society, p. 4, ISBN 9780821886311, https://books.google.com/books?id=qYuC1WsDKq8C&pg=PA4 . Because of this application, de Koninck calls these numbers "horse numbers", but this name does not appear to be in widespread use.
  2. Mendelson, Elliott (1982), "Races with ties", Mathematics Magazine 55 (3): 170–175, doi:10.2307/2690085 
  3. 3.0 3.1 3.2 Sklar, Abe (1952), "On the factorization of squarefree integers", Proceedings of the American Mathematical Society 3 (5): 701–705, doi:10.1090/S0002-9939-1952-0050620-1 
  4. Ziegler, Günter M. (1995), Lectures on Polytopes, Graduate Texts in Mathematics, 152, Springer, p. 18 
  5. Cayley, A. (1859), "On the analytical forms called trees, second part", Philosophical Magazine, Series IV 18 (121): 374–378, doi:10.1017/CBO9780511703706.026, ISBN 9781108004961, https://rcin.org.pl/dlibra/publication/edition/125140/content , in Collected Works of Arthur Cayley, p. 113
  6. Mor, M. (1984), "Cayley permutations", Discrete Mathematics 48 (1): 101–112, doi:10.1016/0012-365X(84)90136-5 
  7. 7.0 7.1 7.2 7.3 "The hypercube of resistors, asymptotic expansions, and preferential arrangements", Mathematics Magazine 83 (5): 331–346, 2010, doi:10.4169/002557010X529752 
  8. Whitworth, W. A. (1886), Choice and Chance, Deighton: Bell and Co., Proposition XXII, p. 93 , as cited by (Pippenger 2010)
  9. Comtet, Louis (1974), Advanced Combinatorics: The Art of Finite and Infinite Expansions (revised and enlarged ed.), D. Reidel Publishing Co., p. 228, http://www.plouffe.fr/simon/math/AdvancedComb.pdf, retrieved 2013-03-12 
  10. 10.0 10.1 10.2 Knopfmacher, A.; Mays, M. E. (2005), "A survey of factorization counting functions", International Journal of Number Theory 1 (4): 563–581, doi:10.1142/S1793042105000315 
  11. 11.0 11.1 "The number of orderings of n candidates when ties are permitted", Fibonacci Quarterly 13: 11–18, 1975, http://www.fq.math.ca/Scanned/13-1/good.pdf 
  12. 12.0 12.1 12.2 Sprugnoli, Renzo (1994), "Riordan arrays and combinatorial sums", Discrete Mathematics 132 (1–3): 267–290, doi:10.1016/0012-365X(92)00570-H 
  13. 1, 14, 36, 24 is the fourth row of this triangle: see Sloane, N. J. A., ed. "Sequence A019538". OEIS Foundation. https://oeis.org/A019538. 
  14. 14.0 14.1 14.2 Velleman, Daniel J.; Call, Gregory S. (1995), "Permutations and combination locks", Mathematics Magazine 68 (4): 243–253, doi:10.2307/2690567 
  15. Getu, Seyoum (1992), "How to guess a generating function", SIAM Journal on Discrete Mathematics 5 (4): 497–499, doi:10.1137/0405040 
  16. Lewis, Barry (2010), "Revisiting the Pascal matrix", American Mathematical Monthly 117 (1): 50–66, doi:10.4169/000298910X474989 
  17. 17.0 17.1 Bailey, Ralph W. (1998), "The number of weak orderings of a finite set", Social Choice and Welfare 15 (4): 559–562, doi:10.1007/s003550050123 
  18. 18.0 18.1 18.2 Gross, O. A. (1962), "Preferential arrangements", The American Mathematical Monthly 69 (1): 4–8, doi:10.2307/2312725 
  19. Barthélémy, J.-P. (1980), "An asymptotic equivalent for the number of total preorders on a finite set", Discrete Mathematics 29 (3): 311–313, doi:10.1016/0012-365X(80)90159-4 
  20. Kauffman, Dolores H. (1963), "Note on preferential arrangements", The American Mathematical Monthly 70 (1): 62, doi:10.2307/2312790 .
  21. "Periodicity of a combinatorial sequence", Fibonacci Quarterly 26 (1): 70–76, 1988 
  22. Petković, Miodrag (2009), Famous Puzzles of Great Mathematicians, American Mathematical Society, p. 194, ISBN 9780821886304, https://books.google.com/books?id=pmSftwkAocAC&pg=PA194 
  23. Harris, John; Hirst, Jeffry L.; Mossinghoff, Michael J. (2008), Combinatorics and Graph Theory, Undergraduate Texts in Mathematics (2nd ed.), Springer, p. 132, ISBN 9780387797106, https://books.google.com/books?id=CxSoZcNymacC&pg=PA132 
  24. 24.0 24.1 Ellison, 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 
  25. Kemeny, John G. (1956), "Two measures of complexity", The Journal of Philosophy 52 (24): 722–733, doi:10.2307/2022697