10657

# Probability of a Union by the Principle of Inclusion-Exclusion

This Demonstration calculates the probability that there is at least one element from each of at most six classes when a given number of elements is sampled without replacement from among all the elements. This probability can be expressed in terms of the probability of a union of events and is calculated using the principle of inclusion-exclusion.

### DETAILS

Snapshot 1: This is an example from [1, p. 73]; the same example is also considered in [2, p. 237]. We have six professors, six associate professors, 10 assistant professors, and 12 instructors; the total number of people is 34. A committee of size six is formed randomly. What is the probability that there is at least one person from each rank on the committee? Snapshot 1 shows that the probability is 0.379031 or, as an exact number, .
Snapshot 2: In a lottery in the USA, five numbers are drawn from the numbers 1 to 59. What is the probability that one number is drawn from each of the five sets , , , , and ? (Each of these sets contains 12 numbers, except the last one that contains 11 numbers.) The probability is only 0.04556. If we choose only 1, 2, 3, or 4 random numbers, the probability that one number is drawn from each of the five sets is, naturally, zero. If we choose 40 random numbers, the probability that one number is drawn from each of the five sets is, to six decimal places, 1.0, but the exact probability shows that the probability becomes exactly 1 only if we choose 49 or more numbers. Indeed, the 48 numbers 1 to 48 can be drawn from the first four sets, but among 49 numbers, there must be some in each of the five sets.
Snapshot 3: In the lottery of Snapshot 2, what is the probability that at least one number is drawn from each of the four sets , , , and ? (These sets contain 15, 15, 15, and 14 numbers, respectively.) The probability is 0.2595.
Snapshot 4: In the same lottery, what is the probability that at least one number is drawn from each of the three sets , , and ? (These sets contain 20, 20, and 19 numbers, respectively.) The probability is 0.6471.
Snapshot 5: Again in the same lottery, what is the probability that at least one number is drawn from each of the two sets and ? (These sets contain 30 and 29 numbers, respectively.) The probability is 0.9478. The probability is the same if the two sets are, say, and . (These sets also contain 30 and 29 numbers, respectively).
In this Demonstration, we have elements in at most six classes. We take a given number of elements at random without replacement from among all of the elements. What is the probability that we get at least one element from each class? Let be the event that we get at least one element from class . We want to calculate . By de Morgan's law, this probability can also be written as . Thus, we arrive at the probability of a union, where is the complement of , that is, is the event that we get no elements from class .
The probability of a union can be calculated by using the principle of inclusion-exclusion. For example,
,
,
In sampling without replacement, the probabilities in these formulas can easily be calculated by binomial coefficients. In the example of Snapshot 1, we have to use the third formula above. The probability that we get no professors is , the probability that we get no professors and no associate professors is , the probability that we get no professors, no associate professors, and no assistant professors is , and so on.
References
[1] S. Ghahramani, Fundamentals of Probability with Stochastic Processes, 3rd ed., Upper Saddle River, NJ: Pearson, 2005.
[2] P. J. Nahin, Digital Dice: Computational Solutions to Practical Probability Problems, Princeton, NJ: Princeton University Press, 2008.

### PERMANENT CITATION

 Share: Embed Interactive Demonstration New! Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details » Download Demonstration as CDF » Download Author Code »(preview ») Files require Wolfram CDF Player or Mathematica.

#### Related Topics

 RELATED RESOURCES
 The #1 tool for creating Demonstrations and anything technical. Explore anything with the first computational knowledge engine. The web's most extensive mathematics resource. An app for every course—right in the palm of your hand. Read our views on math,science, and technology. The format that makes Demonstrations (and any information) easy to share and interact with. Programs & resources for educators, schools & students. Join the initiative for modernizing math education. Walk through homework problems one step at a time, with hints to help along the way. Unlimited random practice problems and answers with built-in step-by-step solutions. Practice online or make a printable study sheet. Knowledge-based programming for everyone.