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).[1] Starting from n = 0, these numbers are

1, 1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563, ... (sequence A000670 in the OEIS).
The 13 possible strict weak orderings on a set of three elements {a, b, c}

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[2] or the faces of all dimensions of a permutohedron[3] (e.g. the sum of faces of all dimensions in the truncated octahedron is 1 + 14 + 36 + 24 = 75[4]).


Share this article:

This article uses material from the Wikipedia article Ordered Bell number, and is written by contributors. Text is available under a CC BY-SA 4.0 International License; additional terms may apply. Images, videos and audio are available under their respective licenses.