Ordered Bell numbers OB(n): count ordered set partitions of [n]. Build by choosing first tier (non-empty subset), then ordering the rest: OB(n)=Σ_{k=1}^{n}C(n,k)·OB(n-k), OB(0)=1. Same as Fubini numbers with compositional emphasis.
How to Use
Enter n:
- OB(n): Ordered Bell
- Recurrence: Step-by-step
- Tiers: By tier count
Recurrence
OB(n) = Σ_{k=1}^{n} C(n,k)·OB(n-k). Choose k items for the first 'tier' in C(n,k) ways, then order the remaining n-k items into tiers in OB(n-k) ways. This compositional recurrence is elegant and efficient.
Generating Function
EGF: Σ OB(n)·x^n/n! = 1/(2-e^x). The singularity at x=ln 2 determines asymptotics. This is one of the simplest EGFs with a natural combinatorial interpretation.
Step-by-Step Instructions
- 1Enter n.
- 2Compute OB(n).
- 3See recurrence.
- 4View tiers.
- 5Check sequence.