In a partition of the set k the number k is either in a bloc

In a partition of the set |k|, 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(k, n), valid for k and n larger than one. Online hint.

Solution

S(k,n) = S(k-1,n)*n + S(k-1,n-1)

if we partition (k-1) into n parts the kth number can go in any part, so total number of cases are multiplied by n.

if we partition (k-1) into n-1 part , the kth number is itself one part