Letters and Envelopes - the Inclusion-Exclusion Principle

Date: 03/27/99 at 20:54:03
From: Jarrad Smith
Subject: Rabbits
 
A warren of rabbits are playing outside their individual burrows when
they are surprised by an eagle. Each rabbit escapes down the nearest 
hole, one rabbit per hole. What is the probability that no rabbit is 
in its own individual hole?
 
Additional info:

1. When there are 6 rabbits, the probability is 0.368.
2. You are not given an exact number of rabbits - simplify the 
   problem and look for patterns to emerge.
3. There is no one correct method - talk to other students to see how 
   they are thinking. Try looking on the Internet.
 
I was just wondering if you had any ideas.

Date: 03/28/99 at 05:21:23
From: Doctor Anthony
Subject: Re: Rabbits

This is a question that usually appears in the guise of letters being 
placed at random into envelopes, and the probability that every letter 
ends up in a wrong envelope. I will start with the situation of 5 letters 
and envelopes, but the principle applies to any objects (such as rabbits 
in holes), and can be extended to any number.

Letters and Envelopes
---------------------
If we let A be the event that letter A is in the correct envelope, and 
similarly B is event that letter B is in the correct envelope, then

P(A) = 1/5  

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

Now use the inclusion, exclusion formula to get the probability that A or 
B or C .... or E are correctly placed. (See later note on the Inclusion-
Exclusion principle.)

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 x (1/5)
                           - 5C2 x (1/5)(1/4)
                           + 5C3 x (1/5)(1/4)(1/3)
                           - 5C4 x (1/5)(1/4)(1/3)(1/2)
                           + (1/5)(1/4)(1/3)(1/2)(1/1)

      5x4    1     5x4x3      1      5x4x3x2      1          1
 1 - ---- x ---- + ------ x ----- - --------- x ------- + --------
      1x2   5x4    1x2x3    5x4x3    1x2x3x4    5x4x3x2   5x4x3x2x1

      = 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 - (the above result)

    = 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

Inclusion-Exclusion Principle
------------------------------
We can use a Venn diagram to illustrate the principle with two or three 
probabilities.

For example: with two overlapping probabilities P(A), P(B), we have 

   P(A or B) = P(A) + P(B) - P(A and B)

The overlapping region is accounted for once with P(A) and again with P(B), 
so to account for it once only we subtract P(A and B), giving rise to the 
expression shown above.

With three overlapping probabilities P(A), P(B) and P(C) we get

P(A or B or C) = P(A) + P(B) + P(C) 
                 - P(A and B) - P(B and C) - P(C and A)
                 + P(A and B and C)

now the overlap of all 3 probabilities is added 3 times by the 
first line of this equation, subtracted 3 times by the second line of 
the equation and so must be added again by the third line.

The area corresponding to A and B but not C is added twice in the 
first line and subtracted once in the second line, so it will appear 
once, as is required. The same is repeated for area B and C but not A,
and the area corresponding to C and A but not B, so each will 
eventually appear once only.

With more probabilities, the pattern continues, and the proof by 
induction is not difficult but a little tedious. The name 'inclusion-
exclusion' describes exactly what is happening: regions are being 
added a number of times and subtracted a number of times in such a way 
that each region occurs exactly once.

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