← Back to the home page

(S, r)-Fubini number

Fn,S,rF_{n, S, r} is the number of linearly ordered partitions of an (n+r)(n+r) element set into blocks, such that each block has cardinality belonging to some set SS, and there are rr distinguished elements in separate blocks.

Recurrence

Fn,S,r=∑s∈S(ns)Fn−s,S,r+r∑s∈S(ns−1)Fn−(s−1),S,r−1F_{n, S, r} = \sum_{s \in S} \binom{n}{s} F_{n-s, S, r} + r \sum_{s \in S} \binom{n}{s-1} F_{n-(s-1), S, r-1}

Formulas

Fn,S,r=∑k=0n(k+r)!{nk}S,rF_{n, S, r} = \sum_{k=0}^n (k + r)! \left\{ {n \atop k} \right\}_{S, r}Fn,S,r=r!2r+1∑ℓ=0∞12ℓ(r+ℓℓ)∑k=0n(nk){nk}S,r(ℓ)kF_{n, S, r} = \frac{r!}{2^{r+1}} \sum_{\ell=0}^\infty \frac{1}{2^\ell} \binom{r + \ell}{\ell} \sum_{k=0}^n \binom{n}{k} \left\{ {n \atop k} \right\}_{S, r} (\ell)_k

Generating Function

∑n=0∞Fn,S,rxnn!=r!(1−ES(x))r+1(∑s∈Sxs−1(s−1)!)r\sum_{n=0}^\infty F_{n, S, r} \frac{x^n}{n!} = \frac{r!}{(1 - E_S(x))^{r+1}} \left( \sum_{s \in S} \frac{x^{s-1}}{(s-1)!} \right)^r

ES(x)=∑s∈Sxss!E_S(x) = \sum_{s \in S} \frac{x^s}{s!}

References

Bényi, Méndez, Ramirez: GENERALIZED ORDERED SET PARTITIONS

Comments

Loading comments...