← Back to the home page

(S, r)-Lah numbers

⌊nk⌋S,r\left\lfloor {n \atop k} \right\rfloor_{S, r} is the number of partitions of an (n+r)(n + r) element set into (k+r)(k + r) lists, where a list means a non-empty, linearly ordered subset, such that rr distinguished elements have to be in distinct ordered blocks, and each block has cardinality belonging to some set SS.

Recurrence

⌊n+1k⌋S,r=⌊nk−1⌋S,r+1+r∑s∈Ss!(ns−2)⌊n−s+2k⌋S,r−1\left\lfloor {n+1 \atop k} \right\rfloor_{S, r} = \left\lfloor {n \atop k-1} \right\rfloor_{S, r+1} + r \sum_{s \in S} s! \binom{n}{s-2} \left\lfloor {n-s+2 \atop k} \right\rfloor_{S, r-1}

Identitites

k⌊nk⌋S,r=∑s∈Ss!(ns)⌊n−sk−1⌋S,rk \left\lfloor {n \atop k} \right\rfloor_{S, r} = \sum_{s \in S} s! \binom{n}{s} \left\lfloor {n-s \atop k-1} \right\rfloor_{S, r} r⌊nk⌋S,r=r∑s∈Ss!(ns−1)⌊n−s+1k⌋S,r−1r \left\lfloor {n \atop k} \right\rfloor_{S, r} = r \sum_{s \in S} s! \binom{n}{s-1} \left\lfloor {n-s+1 \atop k} \right\rfloor_{S, r-1} (n+r)⌊nk⌋S,r=∑s∈Ss!s(ns)⌊n−sk−1⌋S,r+r∑s∈Ss!s(ns−1)⌊n−s+1k⌋S,r−1(n + r) \left\lfloor {n \atop k} \right\rfloor_{S, r} = \sum_{s \in S} s! s \binom{n}{s} \left\lfloor {n-s \atop k-1} \right\rfloor_{S, r} + r \sum_{s \in S} s! s \binom{n}{s-1} \left\lfloor {n-s+1 \atop k} \right\rfloor_{S, r-1}

Generating Function

∑n=k∞⌊nk⌋S,rxnn!=1k!(∑s∈Sxs)k(∑s∈Ssxs−1)r\sum_{n=k}^\infty \left\lfloor {n \atop k} \right\rfloor_{S, r} \frac{x^n}{n!} = \frac{1}{k!} \left( \sum_{s \in S} x^s \right)^k \left( \sum_{s \in S} s x^{s-1} \right)^r

References

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

Comments

Loading comments...