Basic enumeration

Question.

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?

Hint:

Decide now about the postcards. The answer to this question is $n! {k \choose n}$ .

Solution:

I. We have to decide about the postcards independently. Any postcard can be sent to any of the n friends. Hence, the result if $n^{k}$ .

II. Let $C_{1},C_{2}\ldots C_{k}$ be the cards. The set $S=\{ C_{1},C_{2},\ldots C_{k}\}$ must be split into n disjoint non-empty sets $S_{1},\ldots, S_{n}$ . Thus, $\{ S_{1},S_{2}\ldots S_{n}\}$ is a partition of S. From any partition of S into n (non-empty) classes we get $n!$ possibilities to send out the postcards. Hence, the answer is $n! {k \choose n}$ .