<-- Back to the home page

Associated Stirling Numbers of the Second Kind

{nk}≥m\left\{ \begin{matrix} n\\ k \end{matrix} \right\} _{\ge m}

is the number of ways of partitioning an nn element set into kk subsets such that each subset has at least mm elements. They are often called "Associated Stirling numbers" or "r-Associated Stirling numbers".

Basic Recurrence

{n0}≥m={0n}≥m=0 for n>0\left\{ \begin{matrix} n\\ 0 \end{matrix} \right\} _{\ge m} = \left\{ \begin{matrix} 0\\ n \end{matrix} \right\} _{\ge m} = 0 \text{ for } n > 0

{00}≥m=1\left\{ \begin{matrix} 0\\ 0 \end{matrix} \right\} _{\ge m} = 1

{n+1k}≥m=∑i=m−1n(ni){n−ik−1}≥m=k{nk}≥m+(nm−1){n−m+1k−1}≥m\begin{align*} \left\{ {n+1 \atop k} \right\}_{\geq m} &= \sum_{i=m-1}^n \binom{n}{i} \left\{ {n-i \atop k-1} \right\}_{\geq m} \\ &= k \left\{ {n \atop k} \right\}_{\geq m} + \binom{n}{m-1} \left\{ {n-m+1 \atop k-1} \right\}_{\geq m} \end{align*}

Formulas

No explicit formula to calculate these numbers is known. If you find one, please let me know!

Identities

{nk}≥h=0 for n<k∗h\left\{ \begin{matrix} n\\ k \end{matrix} \right\} _{\ge h} = 0 \text{ for } n < k*h

Generating functions

Exponential generating function

∑n=mk∞{nk}≥mxnn!=1k!(ex−Em−1(x))k\sum_{n=mk}^{\infty} \left\{ {n \atop k} \right\}_{\geq m} \frac{x^n}{n!} = \frac{1}{k!} \left( e^x - E_{m-1}(x) \right)^k

Em(t)=∑k=0mtkk!E_m(t) = \sum_{k=0}^{m} \frac{t^k}{k!}

Relation to restricted stirling numbers

{nk}≤∞={nk}≥1={nk}\left\{ {n \atop k} \right\}_{\leq \infty} = \left\{ {n \atop k} \right\}_{\geq 1} = \left\{ {n \atop k} \right\}

Restricted Stirling Numbers

Associated Bell Numbers

Sources

Incomplete poly-Bernoulli numbers associated with incomplete Stirling numbers

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 222.