← 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.

Cases

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*}

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!}

Sources

Comments

Loading comments...