Associated Topics || Dr. Math Home || Search Dr. Math

### Letters and Envelopes - the Inclusion-Exclusion Principle

```
Date: 03/27/99 at 20:54:03
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?

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/
```
Associated Topics:
High School Permutations and Combinations
High School Probability

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search