= Solution
Fix one distinguished element $a$ of the $n$-element <set>. Every <partition of a set> into $l$ blocks belongs to exactly one of two cases. If $\{a\}$ is a block, removing it leaves an $(l-1)$-block <partition of a set> of the other $n-1$ elements, giving $S(n-1,l-1)$ possibilities. Otherwise remove $a$ from its block; that block remains nonempty, so the result has $l$ blocks. Conversely choose any of the $S(n-1,l)$ such partitions and insert $a$ in any one of its $l$ blocks. This gives $lS(n-1,l)$ possibilities.
These cases are disjoint and exhaustive, proving the <Stirling numbers of the second kind> recurrence
$$
\boxed{S(n,l)=lS(n-1,l)+S(n-1,l-1).}
$$
Use $S(0,0)=1$, $S(n,0)=0$ for $n>0$, and $S(n,l)=0$ for $l>n$; these conventions include the boundary cases $n=1$ and $l=1$.
Back to article page
