In number theory and enumerative combinatorics, the ordered Bell numbers or Fubini numbers count the number of weak orderings on a set of 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 , these numbers are
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]
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. [5] 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". [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 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 -element set into 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, , that counts the number of these permutations: [11] [12]
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 . [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]
Another summation formula expresses the ordered Bell numbers in terms of the Eulerian numbers, which count the number of permutations of items with runs of increasing items: [14]
where is the th Eulerian polynomial. [14]
The exponential generating function of the ordered Bell numbers is [7] [10] [12] [15]
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 , where is the identity matrix and 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]
and approximated (by keeping only the term of the sum) as [3] [12] [18] [19] [17]
As well as the formulae above, the ordered Bell numbers may be calculated by the recurrence relation [7] [18]
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 ,
Several additional modular identities are given by Good (1975) and Poonen (1988). [11] [21]
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 items is a factorial number , [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 (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. [14]
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. [24]
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or process of changing the linear order of an ordered set.
In mathematics, the Euler numbers are a sequence En of integers defined by the Taylor series expansion
In mathematics, Stirling numbers arise in a variety of analytic and combinatorial problems. They are named after James Stirling, who introduced them in a purely algebraic setting in his book Methodus differentialis (1730). They were rediscovered and given a combinatorial meaning by Masanobu Saka in 1782.
In number theory and combinatorics, a partition of a non-negative integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. For example, 4 can be partitioned in five distinct ways:
In combinatorial mathematics, the Bell numbers count the possible partitions of a set. These numbers have been studied by mathematicians since the 19th century, and their roots go back to medieval Japan. In an example of Stigler's law of eponymy, they are named after Eric Temple Bell, who wrote about them in the 1930s.
In number theory, the partition functionp(n) represents the number of possible partitions of a non-negative integer n. For instance, p(4) = 5 because the integer 4 has the five partitions 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 3, 2 + 2, and 4.
In mathematics, the double factorial of a number n, denoted by n‼, is the product of all the positive integers up to n that have the same parity as n. That is,
In mathematics, a pyramid number, or square pyramidal number, is a natural number that counts the number of stacked spheres in a pyramid with a square base. The study of these numbers goes back to Archimedes and Fibonacci. They are part of a broader topic of figurate numbers representing the numbers of points forming regular patterns within different shapes.
In mathematics, particularly in combinatorics, a Stirling number of the second kind is the number of ways to partition a set of n objects into k non-empty subsets and is denoted by or . Stirling numbers of the second kind occur in the field of mathematics called combinatorics and the study of partitions. They are named after James Stirling.
In mathematics, especially in combinatorics, Stirling numbers of the first kind arise in the study of permutations. In particular, the Stirling numbers of the first kind count permutations according to their number of cycles.
The Steinhaus–Johnson–Trotter algorithm or Johnson–Trotter algorithm, also called plain changes, is an algorithm named after Hugo Steinhaus, Selmer M. Johnson and Hale F. Trotter that generates all of the permutations of elements. Each two adjacent permutations in the resulting sequence differ by swapping two adjacent permuted elements. Equivalently, this algorithm finds a Hamiltonian cycle in the permutohedron, a polytope whose vertices represent permutations and whose edges represent swaps.
In combinatorics, the twelvefold way is a systematic classification of 12 related enumerative problems concerning two finite sets, which include the classical problems of counting permutations, combinations, multisets, and partitions either of a set or of a number. The idea of the classification is credited to Gian-Carlo Rota, and the name was suggested by Joel Spencer.
In combinatorics, the Eulerian number is the number of permutations of the numbers 1 to in which exactly elements are greater than the previous element.
The use of exponential generating functions (EGFs) to study the properties of Stirling numbers is a classical exercise in combinatorial mathematics and possibly the canonical example of how symbolic combinatorics is used. It also illustrates the parallels in the construction of these two types of numbers, lending support to the binomial-style notation that is used for them.
In mathematics, the permutohedron (also spelled permutahedron) of order n is an (n − 1)-dimensional polytope embedded in an n-dimensional space. Its vertex coordinates (labels) are the permutations of the first n natural numbers. The edges identify the shortest possible paths (sets of transpositions) that connect two vertices (permutations). Two permutations connected by an edge differ in only two places (one transposition), and the numbers on these places are neighbors (differ in value by 1).
In combinatorial mathematics, the ménage problem or problème des ménages asks for the number of different ways in which it is possible to seat a set of male-female couples at a round dining table so that men and women alternate and nobody sits next to his or her partner. This problem was formulated in 1891 by Édouard Lucas and independently, a few years earlier, by Peter Guthrie Tait in connection with knot theory. For a number of couples equal to 3, 4, 5, ... the number of seating arrangements is
In computer science and discrete mathematics, an inversion in a sequence is a pair of elements that are out of their natural order.
In combinatorial mathematics, a partial permutation, or sequence without repetition, on a finite set S is a bijection between two specified subsets of S. That is, it is defined by two subsets U and V of equal size, and a one-to-one mapping from U to V. Equivalently, it is a partial function on S that can be extended to a permutation.
In combinatorics, the Schröder–Hipparchus numbers form an integer sequence that can be used to count the number of plane trees with a given set of leaves, the number of ways of inserting parentheses into a sequence, and the number of ways of dissecting a convex polygon into smaller polygons by inserting diagonals. These numbers begin
In mathematics, the telephone numbers or the involution numbers form a sequence of integers that count the ways n people can be connected by person-to-person telephone calls. These numbers also describe the number of matchings of a complete graph on n vertices, the number of permutations on n elements that are involutions, the sum of absolute values of coefficients of the Hermite polynomials, the number of standard Young tableaux with n cells, and the sum of the degrees of the irreducible representations of the symmetric group. Involution numbers were first studied in 1800 by Heinrich August Rothe, who gave a recurrence equation by which they may be calculated, giving the values