Probability of Matching Envelopes and Letters

Date: 03/03/98 at 04:20:34
From: Raveen Dey
Subject: Probability- permuatations

Six letters were to be placed in envelopes for posting. Unfortunately, 
the letters were dropped before being put in their envelopes, and they 
were placed in at random. 

a) What is the probability that none is in the correct envelope?
b) What is the probability that exactly one is in the correct 
envelope?

Answers
a)53/144
b)11/30

Date: 03/03/98 at 08:14:40
From: Doctor Anthony
Subject: Re: Probability- permutations

I answered a nearly identical question earlier today, so I will copy 
that answer here. I was considering 5 letters and 5 envelopes.

If we let A be the event that letter A is in ist correct envelope and 
similarly B is the event that letter B is in its correct envelope, 
then

P(A) = 1/5 and

P(A and B) = 1/5 * 1/4

Now use the inclusion-exclusion principle to get probability that A or 
B or C .... or E are correctly placed.

P(A or B or C .... or E) = P(A) + P(B) + P(C) + P(D) + P(E)
                          - P(A and B) - P(B and C) -....
                          + P(A and B and C) + P(B and C and D) + ....
                          - P(A and B and C and D) - P(...) -......
                          + P(A and B and C and D and E)

                         = 5*(1/5)
                          - 5C2*(1/5)(1/4)
                          + 5C3*(1/5)(1/4)(1/3)
                          - 5C4*(1/5)(1/4)(1/3)(1/2)
                          + (1/5)(1/4)(1/3)(1/2)(1/1)

        5*4    1    5*4*3     1      5*4*3*2       1          1
  = 1 - --- * --- + ----- * ----- - --------- * ------- + ---------
        1*2   5*4   1*2*3   5*4*3    1*2*3*4    5*4*3*2   5*4*3*2*1

  = 1 - 1/2! + 1/3! - 1/4! + 1/5!

This is the probability that at least one letter is correctly placed.

The chance that none is correctly placed is 1 - (above result), or

  = 1 - 1 + 1/2! - 1/3! + 1/4! - 1/5!

  = 1/2! - 1/3! + 1/4! - 1/5!

With n letters and envelopes, the probability that none is correctly 
placed is:

  = 1/2! - 1/3! + 1/4! - 1/5! + ....... + (-1)^n 1/n!

Note that as n becomes very large, this probability tends to the value 
e^(-1), since:

  e^(-1) = 1 - 1 + 1/2! - 1/3! + 1/4! - ........ to infinity

         = 0.367879...

With six letters and envelopes, the probability that none is correctly 
placed is:

   = 1/2! - 1/3! + 1/4! - 1/5! + 1/6!

   = 1/2 - 1/6 + 1/24 - 1/120 + 1/720

   = 53/144.

To find the probability that exactly one is correctly placed, we need 
to find the total number of ways with 1 correct and 5 incorrect.

We can use the result of the last problem to see the number of ways 
where 5 letters are all incorrect.

If we had 5 letters and 5 envelopes, the probability that all are 
incorrect is 1/2! - 1/3! + 1/4! - 1/5!

Therefore the number of arrangements with all incorrect is given by

    5!(1/2! - 1/3! + 1/4! - 1/5!) = 44

Now imagine the letters laid out in a row, and the envelopes in a 
matching row.

If the first letter is the only correct one opposite its envelope, 
then there are 44 arrangements for the other 5 all putting them in the 
incorrect envelope. Similarly, if the second one is the only correct 
one, then this can be associated with 44 arrangements for the other 5, 
which will all be incorrect. Similarly, for third, fourth, fifth and 
sixth letters, they can each be associated with 44 arrangements, 
making the other 5 all incorrect.

So the total number of arrangements in which just one is correctly 
placed is:

    6 x 44 = 264

The total number of possible arrangements is of course 6! = 720, so 
the probability that exactly one is correct is

    264/720 =  11/30

-Doctor Anthony, The Math Forum
 http://mathforum.org/dr.math/