3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Maybe this is just me but I feel like this question screams derangements/subfactorial (en.wikipedia.org/wiki/Derangement) and that your answer might be $!n$ in that light. Not sure if it's something you would know about or how deeply involved that notion is with this sort of problem. The last bit of the section on "Counting Derangements" does touch on inclusion-exclusion though. $\endgroup$ – Eevee Trainer Nov 18 '18 at 18:25
  • 1
    $\begingroup$ Google for derangements. By the inclusion-exclusion principle, the answer is given by $n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$. $\endgroup$ – Jack D'Aurizio Nov 18 '18 at 18:25
  • 1
    $\begingroup$ There are only two derangements of three objects. However, there are eight ways to distribute three objects to three people so that no person receives the present that he or she brought. In a derangement, each person receives one present, but that is not the case here. $\endgroup$ – N. F. Taussig Nov 18 '18 at 18:35
  • $\begingroup$ @N.F.Taussig: You make a good point about the wording of the problem, but the OP also reports that the answer $(n-1)^n$ was marked incorrect. If the source of this error is not related to the issue of whether each guest must receive a prize, it might instead be connected to the description "there are (n-1) possible prize for each of the n guest." A better argument is that there are $(n-1)$ possible recipients for each of the $n$ prizes brought by guests (assuming all the prizes are distinct). $\endgroup$ – hardmath Nov 18 '18 at 18:47
  • $\begingroup$ Thanks to you guys, I found out a helpful video that taught me how to do derangement! Here is the link if anyone is interested in finding out the answer youtube.com/… $\endgroup$ – Linh Dương Phương Nov 18 '18 at 19:09
1
$\begingroup$

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|$$

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.