###### Problem 134

In a partition of the set \([k]\text{,}\) the number \(k\) is either in a block by itself, or it is not. How does the number of partitions of \([k]\) with \(n\) parts in which \(k\) is in a block with other elements of \([k]\) compare to the number of partitions of \([k-1]\) into \(n\) blocks? Find a two variable recurrence for \(S(n,k)\text{,}\) valid for \(n\) and \(k\) larger than one.

The number of partitions of \([k]\) into \(n\) parts in which \(k\) is not in a block relates to the number of partitions of \(k-1\) into some number of blocks in a way that involves \(n\text{.}\) With this in mind, review how you proved Pascal's (recurrence) equation.