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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.