Reduced Stirling numbers of the second kind

$$S^d(n, k)$$ is the number of ways of partitioning the set $\{1, 2, ..., n\}$ into $k$ subsets such that in each subset, elements have pairwise distance at least $d$.

Recurrence

• $$S^d(1, 1) = 1$$
• $$S^d(1, 0) = 0 \text{ for } n \geq 2$$
• $$S^d(n, k) = 0 \text{ for } k \geq n$$
• $$S^d(n, k) = S^d(n-1, k-1) + (k - d + 1) * S^d(n-1, k) \text{ for } n \geq k \geq d$$

Formula

$$S^d(n, k) = \left\{\begin{matrix}n-d+1\\k-d+1\end{matrix}\right\} \text{ for } n \geq k \geq d$$

Articles

Mohr, Porter: Applications of Chromatic Polynomials Involving Stirling Numbers