Doubly ordered set partitions

← Back to the home page

$D_{n, S, r}$ is the number of partitions of an $(n+r)$ element set into ordered lists, where the order of the lists and of the elements in the lists matter, such that each list has cardinality belonging to some set $S$ , and there are $r$ distinguished elements in separate lists.

Formulas

\mathcal{D}_{n, S, r} = \sum_{k=0}^n k! \left\lfloor {n \atop k} \right\rfloor_{S, r}

\mathcal{D}_{n, S, r} = \frac{r!}{2^{r+1}} \sum_{\ell=0}^\infty \frac{1}{2^\ell} \binom{r+\ell}{\ell} \sum_{k=0}^n \left\lfloor {n \atop k} \right\rfloor_{S, r} (\ell)_k

Recurrence

\mathcal{D}_{n, S, r} = \sum_{s \in S} \binom{n}{s} s \mathcal{D}_{n-s, S, r} + r \sum_{s \in S} \binom{n}{s-1} s \mathcal{D}_{n-(s-1), S, r-1}

Generating Functions

Exponential Generating Function

\sum_{n=0}^\infty \mathcal{D}_{n, S, r} \frac{x^n}{n!} = \frac{r!}{\left( 1 - \sum_{s \in S} x^s \right)^{r+1}} \cdot \left( \sum_{s \in S} s x^{s-1} \right)^r

References

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

Comments