Results 1 to 5 of 5
Like Tree1Thanks
  • 1 Post By a tutor

Math Help - Inclusion Exclusion Principle?

  1. #1
    Newbie
    Joined
    May 2012
    From
    Imaginary Dimension
    Posts
    3

    Inclusion Exclusion Principle?

    Question: n letters belong to n envelopes. How many ways can these be arranged such that each letter is in the wrong envelope?

    I'm quite stuck. I was thinking of applying the Inclusion-Exclusion Principle, so taking:

    (Total combinations = n!) - |A1 u A2 u ... u An|, where Ai is the set where i letters are in the correct envelope.

    I'm not sure if that's the correct method, but even if it is, I'm not sure what to write as the final answer?

    Thanks for any help
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jan 2008
    From
    UK
    Posts
    484
    Thanks
    65

    Re: Inclusion Exclusion Principle?

    I've had this page bookmarked for a while. Still haven't read it. It may give you more help than you want but still..

    http://math.ucr.edu/home/baez/qg-win...erangement.pdf
    Thanks from emakarov
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member Sarasij's Avatar
    Joined
    Jun 2011
    From
    India
    Posts
    42
    Thanks
    2

    Re: Inclusion Exclusion Principle?

    Quote Originally Posted by combinatorixxx View Post
    Question: n letters belong to n envelopes. How many ways can these be arranged such that each letter is in the wrong envelope?

    I'm quite stuck. I was thinking of applying the Inclusion-Exclusion Principle, so taking:

    (Total combinations = n!) - |A1 u A2 u ... u An|, where Ai is the set where i letters are in the correct envelope.

    I'm not sure if that's the correct method, but even if it is, I'm not sure what to write as the final answer?

    Thanks for any help
    See Kenneth Rosen book on Discrete Mathematics and Its Applications,in chapter 6 pg 454 to pg 456
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,412
    Thanks
    1328

    Re: Inclusion Exclusion Principle?

    Put the envelopes in whatever order you want. Choose any letter and put it in any envelope other than the the one it belongs in. There are n-1 ways to do that. Now choose the letter that belongs in that envelope. Choose any of the remaining envelopes to put that one letter in. There are n-1 ways to do that. Proceed in the same manner, at each point, choosing the letter that belongs in the envelope you just filled. That gives a total of (n-1)(n-1)(n-2)...(3)(2)(1)= (n-1)(n-1)! ways to do that.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1

    Re: Inclusion Exclusion Principle?

    Quote Originally Posted by combinatorixxx View Post
    Question: n letters belong to n envelopes. How many ways can these be arranged such that each letter is in the wrong envelope?
    I'm quite stuck. I was thinking of applying the Inclusion-Exclusion Principle, so taking:
    (Total combinations = n!) - |A1 u A2 u ... u An|, where Ai is the set where i letters are in the correct envelope.
    Yes that is correct and you end up with the formula for the number of derangements, \mathcal{D}(n).

    \mathcal{D}(n)=n!\cdot\sum\limits_{k = 0}^n {\frac{{{{\left( { - 1} \right)}^k}}}{{k!}}}

    Now the good news. We do not have to always use that summation.

    This works: \mathcal{D}(n) \approx \frac{{n!}}{e}
    It is very accurate and usual for probability.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Inclusion–exclusion principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 22nd 2011, 05:45 AM
  2. Inclusion Exclusion Principle Help!
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 28th 2011, 02:43 AM
  3. inclusion exclusion principle help!
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 9th 2011, 06:17 AM
  4. Inclusion - Exclusion Principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 15th 2011, 06:52 AM
  5. Principle of Inclusion of Exclusion
    Posted in the Statistics Forum
    Replies: 2
    Last Post: December 10th 2008, 12:15 PM

Search Tags


/mathhelpforum @mathhelpforum