We have k distinct postcards and want to send them all to our friends ( a friend can get any number of postcards, including 0). How many ways can this be done? What happens if we want to send at least one card to each friend?
Decide now about the postcards. The answer to this question is .
I. We have to decide about the postcards independently. Any postcard can be sent to any of the n friends. Hence, the result if .
II. Let be the cards. The set must be split into n disjoint non-empty sets . Thus, is a partition of S. From any partition of S into n (non-empty) classes we get possibilities to send out the postcards. Hence, the answer is .