Number of ways to send out $k$ distinct postcards to $n$ friends if we require each friends receives at least $1$ post card.

Question

This problem comes from the Lovasz Combinatorial Problems and Exercises book. I'm left rather confused for the second half of the second problem. It asks: We have $k$ distinct postcards and want to send them all to our $n$ 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?

The first half is rather simple, however, the second half has me puzzled. This is equivalent to counting the number of surjections yes? However, the answer in the back of the book is $\binom{k}{n}*n!$.

My reasoning gives me that the number of ways to do this would be:

$$n^k-\sum_{i=1}^{n}\binom{n}{i}(n-i)^{k}$$

(something like that I'm typing in a bit of a rush so forgive a mistake if there is one).

But my reasoning is that you count the number of ways to send out the postcards in any manner, and subtract out the ones where you miss some group of $i$ friends. I can't see my error or how my answer is related to the books.

Answer 1

I think you meant $$\sum_{i=0}^n(-1)^i\binom{n}{i}(n-i)^k$$

And what the book meant was using Stirling numbers of the second kind, viz $${k\brace n}n!$$

Answer 2

I believe you're right. The solution given by the textbook, $\binom{k}{n}*n!$ is the number of ways you can send out the $k$ cards such that every friend gets exactly one. (First we assume $k \geq n$). We first choose the $n$ cards to send ($\binom{k}{n}$), next we count every permutation of the chosen cards over the friends (multiply by $n !$).

Obviously this does not count, for example, the possibility that everyone gets at least one card and one gets all leftover cards (which adds $\binom{k}{n-1}*n$ possibilities).

Answer 3

The answer in the book i.e. $\begin{pmatrix}k\\n\end{pmatrix}.n!=\frac{k!}{(k-n)!}$ represents the number of permutations of $n$ objects out of total $k$ distinct objects; which surely is the number of ways to distribute $k$ postcards among $n$ friends so that each gets exactly one. To get the correct answer, you need to further distribute the remaining $k-n$ postcards among $n$ friends without any restriction. Now this can be done in $n^{k-n}$ ways so the correct answer is the product $\frac{k!}{(k-n)!}\times n^{k-n}$.