Ordered Bell number

In number theory and enumerative combinatorics, 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). Starting from n = 0, 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 or the faces of all dimensions of a permutohedron (e.g. the sum of faces of all dimensions in the truncated octahedron is 1 + 14 + 36 + 24 = 75).

The ordered Bell numbers appear in the work of Cayley (1859), who used them to count certain plane trees 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; 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 positive integers that include at least one copy of each positive integer between one and the maximum value in the sequence) "Cayley permutations".

...
Wikipedia