Results 1 to 4 of 4

Math Help - Permutation Problem

  1. #1
    Newbie
    Joined
    Sep 2008
    Posts
    20

    Permutation Problem

    Please help in the following problem...

    There are 8 envelops and 8 corresponding letters. Find the probability that :-
    a) At least 2 letters go to the wrong envelops.
    b) None of the letters go in to the right envelop.

    Please help...any suggestion will be welcomed.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,968
    Thanks
    1785
    Awards
    1
    The answer to the b part is \approx \frac{1}{e}
    I bet you wonder why. Look at the following webpage.
    Derangement -- from Wolfram MathWorld
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,914
    Thanks
    779
    Hello, skyskiers!

    There are 8 envelopes and 8 corresponding letters.
    There are: . 8! = 40,\!320 possible outcomes.


    Find the probability that:

    a) At least 2 letters go to the wrong envelopes.

    This is a bit of a "trick question".

    Is there a way for exactly one letter to be in the wrong envelope?

    Imagine . . . the other 7 letters are in the right envelopes.
    . . Can the 8th one go into a wrong envelope? . . . No.

    So it is impossible for exactly one letter to be misplaced.
    That is, if any are misplaced, there will be at least two misplaced.


    There is exactly one way for the letters be matched to their envelopes.
    . . P(\text{all correct}) \:=\:\frac{1}{40,\!320}

    The rest of the time, there will be at least 2 misplaced.

    Therefore: . P(\text{at least 2 misplaced}) \;=\;1-\frac{1}{40,\!320} \;=\;\frac{40,\!319}{40,\!320}



    b) None of the letters go in to the right envelope.
    This is a messy problem and has an obscure solution.

    An arrangement of n objects in which no object is in its proper position
    . . is a derangement of the n objects.

    We want the number of derangements of 8 objects: d(8)

    It can be found by: . d(8) \;=\;(Q-1)^8\;\;\text{ where }Q^n = n!
    . .
    Imagine . . . an exponent becomes a factorial!

    We have: . (Q-1)^8 \:=\:Q^8 - 8Q^7 + 28Q^6 - 56Q^5 + 70Q^4 - 56Q^3 + 28Q^2 - 8Q + 1

    . . . . . . . . . . . . . =\;8! - 8(7!) + 28(6!) - 56(5!) + 70(4!) - 56(3!) + 28(2!) - 8(1!) + 1

    . . . . . . . . . . . . . = \;40,\!320 - 40,\!320 + 20,\!160 - 6,\!720 + 1,\!680 - 336 + 56 - 8 + 1

    . . . . . . . . . . . . . = \;14,\!833

    Therefore, the probability is: . \frac{14,\!833}{40,\!320} \;=\;\frac{2,\!119}{5,\!760}

    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Sep 2008
    Posts
    20
    Theres only 1 thing I can say....

    You guys are just amazing....awesome..

    Thx
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Permutation problem.
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 11th 2010, 09:39 AM
  2. PERMUTATION problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 25th 2009, 08:10 PM
  3. permutation problem 1
    Posted in the Statistics Forum
    Replies: 1
    Last Post: April 26th 2009, 09:57 PM
  4. permutation problem
    Posted in the Advanced Statistics Forum
    Replies: 6
    Last Post: March 24th 2009, 05:20 PM
  5. Permutation Problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 13th 2008, 12:15 PM

Search Tags


/mathhelpforum @mathhelpforum