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}.

More later,

Nalin Pithwa

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s