<-- Back to the home page

Restricted Stirling Numbers of the Second Kind

{nk}≤m\left\{ \begin{matrix} n\\ k \end{matrix} \right\} _{\le m}

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

Basic Recurrence

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

{00}≤m=1\left\{ \begin{matrix} 0\\ 0 \end{matrix} \right\} _{\le m} = 1

{n+1k}≤m=∑i=0m−1(ni){n−ik−1}≤m=k{nk}≤m+{nk−1}≤m−(nm){n−mk−1}≤m\begin{align*} \left\{ {n+1 \atop k} \right\}_{\leq m} &= \sum_{i=0}^{m-1} \binom{n}{i} \left\{ {n-i \atop k-1} \right\}_{\leq m} \\ &= k \left\{ {n \atop k} \right\}_{\leq m} +\left\{ {n \atop k-1} \right\}_{\leq m} - \binom{n}{m} \left\{ {n-m \atop k-1} \right\}_{\leq 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\} _{\le h} = 0 \text{ for } n > k*h

Generating functions

Exponential generating function

∑n=kmk{nk}≤mxnn!=1k!(Em(x)−1)k\sum_{n=k}^{mk} \left\{ {n \atop k} \right\}_{\leq m} \frac{x^n}{n!} = \frac{1}{k!} \left( E_{m}(x) - 1 \right)^k

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

Relation to associated 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\}

Associated Stirling Numbers

Restricted Bell Numbers

Sources

Incomplete poly-Bernoulli numbers associated with incomplete Stirling numbers