← Back to the home page

Fubini number

FnF_{n} also called "ordered Bell number", it is the number of set partitions of an nn element set into a list of blocks, meaning the blocks are linearly ordered but the elements in them are not.

A000670 on the OEIS

Recurrence

F0=1F_0 = 1Fn=∑i=1n(ni)Fn−iF_n = \sum_{i=1}^n \binom{n}{i} F_{n-i}

Formulas

Fn=∑k=0nk!{nk}F_n = \sum_{k=0}^n k! \left\{ {n \atop k} \right\} Fn=∑k=0n∑j=0k(−1)k−j(kj)jn=12∑m=0∞mn2mF_n = \sum_{k=0}^n \sum_{j=0}^k (-1)^{k-j} \binom{k}{j} j^n = \frac{1}{2} \sum_{m=0}^\infty \frac{m^n}{2^m}

Generating Function

∑n=0∞Fnxnn!=12−ex\sum_{n=0}^\infty F_n \frac{x^n}{n!} = \frac{1}{2 - e^x}

Source

Wikipedia

Comments

Loading comments...