← Back to the home page

(S, r)-Stirling number of the second kind

{nk}S,r\left\{ {n \atop k} \right\}_{S, r} is the number of set partitions of an (n+r)(n+r) element set into (k+r)(k+r) blocks, such that each block has cardinality belonging to some set SS, and there are rr distinguished elements in separate blocks.

Recurrence

{n+1k}S,r={nk−1}S,r+1+r∑s∈S(ns−2){n−s+2k}S,r−1\left\{ {n+1 \atop k} \right\}_{S, r} = \left\{ {n \atop k-1} \right\}_{S, r+1} + r \sum_{s \in S} \binom{n}{s-2} \left\{ {n-s+2 \atop k} \right\}_{S, r-1} k{nk}S,r=∑s∈S(ns){n−sk−1}S,rk \left\{ {n \atop k} \right\}_{S, r} = \sum_{s \in S} \binom{n}{s} \left\{ {n-s \atop k-1} \right\}_{S, r} r{nk}S,r=∑s∈Sr(ns−1){n−s+1k}S,r−1r \left\{ {n \atop k} \right\}_{S, r} = \sum_{s \in S} r \binom{n}{s-1} \left\{ {n-s+1 \atop k} \right\}_{S, r-1} (n+r){nk}S,r=∑s∈Ss(ns){n−sk−1}S,r+r∑s∈Ss(ns−1){n−s+1k}S,r−1(n + r) \left\{ {n \atop k} \right\}_{S, r} = \sum_{s \in S} s \binom{n}{s} \left\{ {n-s \atop k-1} \right\}_{S, r} + r \sum_{s \in S} s \binom{n}{s-1} \left\{ {n-s+1 \atop k} \right\}_{S, r-1}

Generating Function

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

∑r=0∞∑n=0∞(∑k=0n{nk}S,ryk)zrxnr!n!=exp⁡(y∑i≥1xkiki!)exp⁡(z∑i≥1xki−1(ki−1)!)\sum_{r=0}^\infty \sum_{n=0}^\infty \left( \sum_{k=0}^n \left\{ {n \atop k} \right\}_{S, r} y^k \right) \frac{z^r x^n}{r! n!} = \exp\left( y \sum_{i \geq 1} \frac{x^{k_i}}{k_i!} \right) \exp\left( z \sum_{i \geq 1} \frac{x^{k_i-1}}{(k_i-1)!} \right)

References

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

Bényi, Méndez, Ramirez, Wakhare: RESTRICTED r-STIRLING NUMBERS AND THEIR COMBINATORIAL APPLICATIONS

Comments

Loading comments...