# Combinatorial proof of the recurrence relation.

Let $S_i (n,k)$ denote the number of partitions of $[n]$ into $k$ blocks where each block contains at least $i$ elements. Give a combinatorial proof of the following recurrence relation:

$$S_i (n,k) = k S_i (n-1, k)+ \binom {n-1}{i-1} S_i(n-i,k-1)$$

-

The element $n$ is either in a block with exactly $i$ elements or in a block with more than $i$ elements. To generate all partitions where $n$ is in a block with more than $i$ elements, take the partitions of $[n-1]$ into $k$ blocks with at least $i$ elements each and add $n$ to any one of the $k$ blocks – that accounts for the first term. To generate all partitions where $n$ is in a block with exactly $i$ elements, choose $i-1$ elements from $[n-1]$ that are in the same block as $n$ and a partition of the remaining $n-i$ elements into $k-1$ blocks with at least $i$ elements each – that accounts for the second term.

-