$n$ guests, each guest brings a prize, how many ways may the prizes be given out so nobody gets the prize that they brought?

Question

Each person attending a party has been asked to bring a prize. The person planning the party has arranged to give out exactly as many prizes as there are guests, but any person may win any number of the prizes. If there are $n$ guests, in how many ways may the prizes be given out so that nobody gets the prize that they brought?

---

My answer was $(n-1)^n$, for I thought that there are $(n-1)$ possible prizes for each of the $n$ guests. However, my answer is wrong. I'm given a hint that it will involve with the inclusion-exclusion principle, I'm not sure how to interpret the problem in this direction.

Answer 1

Let's mark every prize from 1 to n, p1, p2, p3, ... pn and the people at the guests at the party g1, g2, g3, ... gn, where pi is the prize from guest gi. Your goal is to make sure that you don't match the prizes with the guests that are having the same indices. In this case you need to make sure that: p1 doesn't go to g1, p2 doesn't go to g2, p3 doesn't go to g3, and so on. Let's consider |S| being the case where at least a guest is receiving the same prize. In this case we can write |S| like this: $$|S| = p1\cup p2\cup p3\cup ...\cup pn$$ This can be translated into "Present 1 goes to guest 1 or present 2 goes to guest 2 and so on". If we expand this, we have something like this: $$|S| = \binom{n}{1} - \binom{n}{2} + \binom{n}{3} + ... + (-1)^n\binom{n}{n}$$

In your case, you need the opposite (the number of ways the people DON'T receive the same prize) so what you need to do is to subtract from the total ways you can distribute the prizes |S|. Total number of ways to distribute the n prizes is $n^n$ (not n-1 since you need to count for the case when the person is not receiving anything. Hence:

$$n^n - |S|$$

Answer 2

Derangements count the situation where every guest gets exactly 1 prize. However, the OP wording says that every guest can get ANY number of prizes (i.e. $0$ to $n-1$ since he/she cannot get his/her own prize). In this case, the correct answer is indeed $(n-1)^n$, because each of $n$ prizes can go to any of $(n-1)$ recipients. I.e., your teacher is wrong to mark you wrong.

If your teacher insists on using Inclusion Exclusion, then let $A_i$ be the set of arrangements s.t. person $i$ gets his/her own gift. Then I-E gives:

$answer = n^n - \sum_i |A_i| + \sum_{i<j} |A_i \cap A_j| - \sum_{i<j<k} |A_i \cap A_j \cap A_k| + ...$

Now, $|A_i| = n^{n-1}$ since the other $n-1$ gifts are unconstrained and each can go to any of $n$ recipients. Similarly, $|A_i \cap A_j| = n^{n-2}$ because the other $n-2$ gifts are unconstrained and each can go to any of $n$ recipients. Similarly for higher terms. So:

$answer = n^n - {n \choose 1} n^{n-1} + {n \choose 2} n^{n-2} - {n \choose 3} n^{n-3} + ... = \sum_{k=0}^n {n \choose k} (-1)^k n^{n-k}$

But the last summation is exactly the binomial expansion of $(n-1)^n$.