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











up vote
3
down vote

favorite
1












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.










share|cite|improve this question




















  • 1




    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.
    – Eevee Trainer
    Nov 18 at 18:25






  • 1




    Google for derangements. By the inclusion-exclusion principle, the answer is given by $n!sum_{k=0}^{n}frac{(-1)^k}{k!}$.
    – Jack D'Aurizio
    Nov 18 at 18:25






  • 1




    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.
    – N. F. Taussig
    Nov 18 at 18:35










  • @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).
    – hardmath
    Nov 18 at 18:47












  • 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/…
    – Linh Dương Phương
    Nov 18 at 19:09















up vote
3
down vote

favorite
1












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.










share|cite|improve this question




















  • 1




    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.
    – Eevee Trainer
    Nov 18 at 18:25






  • 1




    Google for derangements. By the inclusion-exclusion principle, the answer is given by $n!sum_{k=0}^{n}frac{(-1)^k}{k!}$.
    – Jack D'Aurizio
    Nov 18 at 18:25






  • 1




    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.
    – N. F. Taussig
    Nov 18 at 18:35










  • @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).
    – hardmath
    Nov 18 at 18:47












  • 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/…
    – Linh Dương Phương
    Nov 18 at 19:09













up vote
3
down vote

favorite
1









up vote
3
down vote

favorite
1






1





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.










share|cite|improve this 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.







combinatorics discrete-mathematics inclusion-exclusion






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Nov 18 at 19:22









N. F. Taussig

42.8k93254




42.8k93254










asked Nov 18 at 18:22









Linh Dương Phương

161




161








  • 1




    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.
    – Eevee Trainer
    Nov 18 at 18:25






  • 1




    Google for derangements. By the inclusion-exclusion principle, the answer is given by $n!sum_{k=0}^{n}frac{(-1)^k}{k!}$.
    – Jack D'Aurizio
    Nov 18 at 18:25






  • 1




    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.
    – N. F. Taussig
    Nov 18 at 18:35










  • @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).
    – hardmath
    Nov 18 at 18:47












  • 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/…
    – Linh Dương Phương
    Nov 18 at 19:09














  • 1




    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.
    – Eevee Trainer
    Nov 18 at 18:25






  • 1




    Google for derangements. By the inclusion-exclusion principle, the answer is given by $n!sum_{k=0}^{n}frac{(-1)^k}{k!}$.
    – Jack D'Aurizio
    Nov 18 at 18:25






  • 1




    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.
    – N. F. Taussig
    Nov 18 at 18:35










  • @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).
    – hardmath
    Nov 18 at 18:47












  • 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/…
    – Linh Dương Phương
    Nov 18 at 19:09








1




1




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.
– Eevee Trainer
Nov 18 at 18:25




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.
– Eevee Trainer
Nov 18 at 18:25




1




1




Google for derangements. By the inclusion-exclusion principle, the answer is given by $n!sum_{k=0}^{n}frac{(-1)^k}{k!}$.
– Jack D'Aurizio
Nov 18 at 18:25




Google for derangements. By the inclusion-exclusion principle, the answer is given by $n!sum_{k=0}^{n}frac{(-1)^k}{k!}$.
– Jack D'Aurizio
Nov 18 at 18:25




1




1




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.
– N. F. Taussig
Nov 18 at 18:35




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.
– N. F. Taussig
Nov 18 at 18:35












@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).
– hardmath
Nov 18 at 18:47






@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).
– hardmath
Nov 18 at 18:47














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/…
– Linh Dương Phương
Nov 18 at 19:09




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/…
– Linh Dương Phương
Nov 18 at 19:09










2 Answers
2






active

oldest

votes

















up vote
0
down vote













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| = p1cup p2cup p3cup ...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)^nbinom{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|$$






share|cite|improve this answer




























    up vote
    0
    down vote













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






    share|cite|improve this answer





















      Your Answer





      StackExchange.ifUsing("editor", function () {
      return StackExchange.using("mathjaxEditing", function () {
      StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
      StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
      });
      });
      }, "mathjax-editing");

      StackExchange.ready(function() {
      var channelOptions = {
      tags: "".split(" "),
      id: "69"
      };
      initTagRenderer("".split(" "), "".split(" "), channelOptions);

      StackExchange.using("externalEditor", function() {
      // Have to fire editor after snippets, if snippets enabled
      if (StackExchange.settings.snippets.snippetsEnabled) {
      StackExchange.using("snippets", function() {
      createEditor();
      });
      }
      else {
      createEditor();
      }
      });

      function createEditor() {
      StackExchange.prepareEditor({
      heartbeatType: 'answer',
      convertImagesToLinks: true,
      noModals: true,
      showLowRepImageUploadWarning: true,
      reputationToPostImages: 10,
      bindNavPrevention: true,
      postfix: "",
      imageUploader: {
      brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
      contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
      allowUrls: true
      },
      noCode: true, onDemand: true,
      discardSelector: ".discard-answer"
      ,immediatelyShowMarkdownHelp:true
      });


      }
      });














      draft saved

      draft discarded


















      StackExchange.ready(
      function () {
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3003917%2fn-guests-each-guest-brings-a-prize-how-many-ways-may-the-prizes-be-given-out%23new-answer', 'question_page');
      }
      );

      Post as a guest















      Required, but never shown

























      2 Answers
      2






      active

      oldest

      votes








      2 Answers
      2






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes








      up vote
      0
      down vote













      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| = p1cup p2cup p3cup ...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)^nbinom{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|$$






      share|cite|improve this answer

























        up vote
        0
        down vote













        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| = p1cup p2cup p3cup ...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)^nbinom{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|$$






        share|cite|improve this answer























          up vote
          0
          down vote










          up vote
          0
          down vote









          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| = p1cup p2cup p3cup ...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)^nbinom{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|$$






          share|cite|improve this answer












          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| = p1cup p2cup p3cup ...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)^nbinom{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|$$







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Nov 18 at 20:38









          Erik Cristian Seulean

          456




          456






















              up vote
              0
              down vote













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






              share|cite|improve this answer

























                up vote
                0
                down vote













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






                share|cite|improve this answer























                  up vote
                  0
                  down vote










                  up vote
                  0
                  down vote









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






                  share|cite|improve this answer












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







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered Nov 18 at 22:13









                  antkam

                  1,373112




                  1,373112






























                      draft saved

                      draft discarded




















































                      Thanks for contributing an answer to Mathematics Stack Exchange!


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid



                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.


                      Use MathJax to format equations. MathJax reference.


                      To learn more, see our tips on writing great answers.





                      Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


                      Please pay close attention to the following guidance:


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid



                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.


                      To learn more, see our tips on writing great answers.




                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function () {
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3003917%2fn-guests-each-guest-brings-a-prize-how-many-ways-may-the-prizes-be-given-out%23new-answer', 'question_page');
                      }
                      );

                      Post as a guest















                      Required, but never shown





















































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown

































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown







                      Popular posts from this blog

                      Ellipse (mathématiques)

                      Quarter-circle Tiles

                      Mont Emei