Ordered Bell Number
   HOME

TheInfoList



OR:

In
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Math ...
and
enumerative combinatorics Enumerative combinatorics is an area of combinatorics that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting combinations and counting permutations. More generally, given an infin ...
, the ordered Bell numbers or Fubini numbers count the number of weak orderings on a set of ''n'' elements (orderings of the elements into a sequence allowing ties, such as might arise as the outcome of a
horse race Horse racing is an equestrian performance sport, typically involving two or more horses ridden by jockeys (or sometimes driven without riders) over a set distance for competition. It is one of the most ancient of all sports, as its basic p ...
).. Because of this application, de Koninck calls these numbers "horse numbers", but this name does not appear to be in widespread use. Starting from ''n'' = 0, these numbers are :1, 1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563, ... . The ordered Bell numbers may be computed via a summation formula involving
binomial coefficient In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...
s, or by using a
recurrence relation In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a paramete ...
. 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 or the faces of all dimensions of a permutohedron (e.g. the sum of faces of all dimensions in the
truncated octahedron In geometry, the truncated octahedron is the Archimedean solid that arises from a regular octahedron by removing six pyramids, one at each of the octahedron's vertices. The truncated octahedron has 14 faces (8 regular hexagons and 6 squares), 36 ...
is 1 + 14 + 36 + 24 = 75).


History

The ordered Bell numbers appear in the work of , who used them to count certain
plane trees ''Platanus'' is a genus consisting of a small number of tree species native to the Northern Hemisphere. They are the sole living members of the family Platanaceae. All mature members of ''Platanus'' are tall, reaching in height. All except ...
with ''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'' from the root must be strictly smaller than the number of nodes at distance ''i'' + 1, until reaching the leaves. In such a tree, there are ''n'' pairs of adjacent leaves, that may be weakly ordered by the height of their
lowest common ancestor In graph theory and computer science, the lowest common ancestor (LCA) (also called least common ancestor) of two nodes and in a tree or directed acyclic graph (DAG) is the lowest (i.e. deepest) node that has both and as descendants, where ...
; 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 ''n'' 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 number of different ways to rearrange the ordering of sums or integrals in Fubini's theorem, which in turn is named after
Guido Fubini Guido Fubini (19 January 1879 – 6 June 1943) was an Italian mathematician, known for Fubini's theorem and the Fubini–Study metric. Life Born in Venice, he was steered towards mathematics at an early age by his teachers and his father, who ...
. For instance, for a bivariate integral, Fubini's theorem states that :\int_A\left(\int_B f(x,y)\,\texty\right)\,\textx=\int_B\left(\int_A f(x,y)\,\textx\right)\,\texty=\int_ f(x,y)\,\text(x,y), where these three formulations correspond to the three weak orderings on two elements. In general, in a multivariate integral, the ordering in which the variables may be grouped into a sequence of nested integrals forms a weak ordering. The
Bell number 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 epony ...
s, named after
Eric Temple Bell Eric Temple Bell (7 February 1883 – 21 December 1960) was a Scottish-born mathematician and science fiction writer who lived in the United States for most of his life. He published non-fiction using his given name and fiction as John Tai ...
, 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 In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexiv ...
on the sets in the partition..


Formula

The ''n''th ordered Bell number may be given by a
summation In mathematics, summation is the addition of a sequence of any kind of numbers, called ''addends'' or ''summands''; the result is their ''sum'' or ''total''. Beside numbers, other types of values can be summed as well: functions, vectors, m ...
formula involving the
Stirling numbers of the second kind In mathematics, particularly in combinatorics, a Stirling number of the second kind (or Stirling partition number) is the number of ways to partition a set of ''n'' objects into ''k'' non-empty subsets and is denoted by S(n,k) or \textstyle \le ...
, which count the number of partitions of an ''n''-element set into ''k'' nonempty subsets,.. expanded out into a double summation involving
binomial coefficient In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...
s (using a formula expressing Stirling numbers as a sum of binomial coefficients), or given by an
infinite series In mathematics, a series is, roughly speaking, a description of the operation of adding infinitely many quantities, one after the other, to a given starting quantity. The study of series is a major part of calculus and its generalization, ma ...
:. :a(n)= \sum_^n k! \left\=\sum_^n \sum_^k (-1)^ \binomj^n=\frac12\sum_^\infty\frac. An alternative summation formula expresses the ordered Bell numbers in terms of the Eulerian numbers, which count the number of permutations of ''n'' items with ''k'' + 1 runs of increasing items:. :a(n)=\sum_^ 2^k \left\langle\begin n \\ k \end\right\rangle=A_n(2), where ''An'' is the ''n''th Eulerian polynomial. The
exponential generating function In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary ser ...
of the ordered Bell numbers is :\sum_^\infty a(n)\frac = \frac. This can be expressed equivalently as the fact that the ordered Bell numbers are the numbers in the first column of the infinite matrix (2''I'' − ''P'')−1, where ''I'' is the
identity matrix In linear algebra, the identity matrix of size n is the n\times n square matrix with ones on the main diagonal and zeros elsewhere. Terminology and notation The identity matrix is often denoted by I_n, or simply by I if the size is immaterial ...
and ''P'' is an infinite matrix form of
Pascal's triangle In mathematics, Pascal's triangle is a triangular array of the binomial coefficients that arises in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, althoug ...
. Based on a contour integration of this generating function, the ordered Bell numbers can be expressed by the infinite sum :a(n)=\frac\sum_^(\log 2+2\pi ik)^,\qquad n\ge1, and approximated as... :a(n)\approx \frac. Because log 2 is less than one, the form of this approximation shows that the ordered Bell numbers exceed the corresponding
factorial In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial: \begin n! &= n \times (n-1) \times (n-2) ...
s by an exponential factor. The asymptotic convergence of this approximation may be expressed as :\lim_ \frac=\log 2.


Recurrence and modular periodicity

As well as the formulae above, the ordered Bell numbers may be calculated by the
recurrence relation In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a paramete ...
:a(n) = \sum_^\binoma(n-i). The intuitive meaning of this formula is that a weak ordering on ''n'' items may be broken down into a choice of some nonempty set of ''i'' items that go into the first equivalence class of the ordering, together with a smaller weak ordering on the remaining ''n'' − ''i'' items. As a base case for the recurrence, ''a''(0) = 1 (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 In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his bo ...
: for sufficiently large ''n'', :a(n+4) \equiv a(n) \pmod, :a(n+20) \equiv a(n) \pmod, :a(n+100) \equiv a(n) \pmod, and :a(n+500) \equiv a(n) \pmod. Several additional modular identities are given by and .


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, or the possible outcomes of a multi-candidate
election An election is a formal group decision-making process by which a population chooses an individual or multiple individuals to hold public office. Elections have been the usual mechanism by which modern representative democracy has opera ...
. 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 Baseball is a bat-and-ball sport played between two teams of nine players each, taking turns batting and fielding. The game occurs over the course of several plays, with each play generally beginning when a player on the fielding ...
players), the number of orderings for ''n'' items is a factorial number ''n''!, which is significantly smaller than the corresponding ordered Bell number. 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. consider
combination lock A combination lock is a type of locking device in which a sequence of symbols, usually numbers, is used to open the lock. The sequence may be entered using a single rotating dial which interacts with several discs or ''cams'', by using a set o ...
s 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. point out an application of these numbers to
optimality theory In linguistics, Optimality Theory (frequently abbreviated OT) is a linguistic model proposing that the observed forms of language arise from the optimal satisfaction of conflicting constraints. OT differs from other approaches to phonological ...
in
linguistics Linguistics is the scientific study of human language. It is called a scientific study because it entails a comprehensive, systematic, objective, and precise analysis of all aspects of language, particularly its nature and structure. Lingu ...
. In this theory, grammars for
natural language In neuropsychology, linguistics, and philosophy of language, a natural language or ordinary language is any language that has evolved naturally in humans through use and repetition without conscious planning or premeditation. Natural languag ...
s 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
factorial In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial: \begin n! &= n \times (n-1) \times (n-2) ...
s, allows this theory to generate a much richer set of grammars..


References

{{Classes of natural numbers Integer sequences Enumerative combinatorics