The Inclusion–Exclusion Principle: Counting and Probability for Overlapping Events

How many students take at least one of three subjects, when many take two or all three? What is the probability that a random number is divisible by 2, 3, or 5? Adding up the sizes of the groups overcounts anyone who belongs to several. The inclusion–exclusion principle fixes this systematically: add everything, subtract the overlaps you counted twice, add back the triple overlaps you subtracted too many times, and continue alternating until every possible overlap has been handled. It is the workhorse for finding the probability that at least one of several events happens when the events are not mutually exclusive.

Two Events

For two events A and B, the probability of A or B is the sum of the two probabilities minus the overlap, which would otherwise be counted twice:

This is the addition rule from basic probability. When the events cannot both happen, the overlap is zero and the rule reduces to simple addition.

Three Events

With three events, subtracting the pairwise overlaps removes the triple overlap one time too many, so it must be added back:

To see why, follow someone who belongs to all three sets. They are counted three times in the singles, subtracted three times in the pairs, and added once in the triple: 3 − 3 + 1 = 1. Every element of the union ends up counted exactly once. The same works for someone in exactly two sets: 2 − 1 = 1.

Worked Example: Overlapping Subjects

Problem: In a group of 100 students, 60 take Maths, 45 take Physics, and 30 take Chemistry. Also, 25 take both Maths and Physics, 15 take both Maths and Chemistry, 12 take both Physics and Chemistry, and 8 take all three. How many take at least one of the three subjects, and how many take none?

Applying the formula to the counts:

So 91 students take at least one subject and 9 take none. The probability that a randomly chosen student takes at least one is 91 ÷ 100 = 0.91.

Checking region by region. Split the Venn diagram into its seven parts. The triple overlap holds 8 students. Maths and Physics only: 25 − 8 = 17. Maths and Chemistry only: 15 − 8 = 7. Physics and Chemistry only: 12 − 8 = 4. Maths only: 60 − 8 − 17 − 7 = 28. Physics only: 45 − 8 − 17 − 4 = 16. Chemistry only: 30 − 8 − 7 − 4 = 11. The seven regions total 28 + 16 + 11 + 17 + 7 + 4 + 8 = 91, matching the formula.

Partial Sums as Bounds

The alternating terms are useful even when cut short. Call the sum of single probabilities S₁ = 135 (in counts), the sum of pairs S₂ = 52, and the triple S₃ = 8. Stopping after the first term overestimates the union (135 is more than the 100 students, a useless bound). Stopping after the second term underestimates it: S₁ − S₂ = 83, below the true 91. Adding the third term lands on the exact value. This pattern, in which successive partial sums alternately overshoot and undershoot, gives the Bonferroni inequalities. The first, P(A ∪ B ∪ …) ≤ ΣP, is the "union bound" behind the Bonferroni correction discussed in the multiple comparisons problem.

Counting Example: Divisibility

Problem: How many integers from 1 to 100 are divisible by 2, 3, or 5?

Let A, B, and C be the sets divisible by 2, 3, and 5. Their sizes are the whole-number parts of 100 divided by each number: 50, 33, and 20. Overlaps are multiples of the product: divisible by 6 (both 2 and 3) gives 16; by 10 gives 10; by 15 gives 6; and divisible by all three (by 30) gives 3. Then:

So 74 of the numbers qualify, and 26 are not divisible by any of 2, 3, or 5. A random integer from 1 to 100 has probability 0.74 of being divisible by at least one. These counts can be verified by direct listing, but the formula scales to conditions that make listing impractical.

Application: No Matches in the Hat Problem

In the matching-hats problem from linearity of expectation, n people receive hats in random order. What is the probability that nobody gets their own hat? Let Eₖ be the event that person k gets their own hat. The probability that a specific set of j people all get their own hats is (n − j)! ÷ n!, and there are C(n, j) such sets, so each level of the formula contributes C(n, j) × (n − j)! ÷ n! = 1 ÷ j!. Inclusion–exclusion gives:

For n = 4, P(no match) = 1 − 1 + 1/2 − 1/6 + 1/24 = 9/24 = 0.375. For n = 5, the series adds another term, −1/120, giving 44/120 ≈ 0.367, which agrees exactly with the 44 no-match arrangements found by listing all 120 permutations in the linearity article. As n grows, the sum converges to 1/e ≈ 0.368. The number of arrangements with no fixed points, called derangements, is n! times this alternating sum. The counting rules themselves come from permutations and combinations.

Probability Version With Independence

When the events are independent, the intersections factor into products, and a shortcut becomes available: P(at least one) = 1 − P(none) = 1 − (1 − P(A))(1 − P(B))(1 − P(C)). For three independent events each with probability 0.2, that is 1 − 0.8³ = 0.488. Inclusion–exclusion gives the same: 3(0.2) − 3(0.04) + 0.008 = 0.6 − 0.12 + 0.008 = 0.488. The complement route is faster when independence holds, and inclusion–exclusion is needed when it does not, or when overlap counts are given directly, as in the survey.

Real-World Uses

Survey and market analysis: counting how many customers used at least one of several products, given overlapping usage figures reported separately.

Reliability and risk: the probability that at least one of several component failures or risk events occurs, where the events can overlap and are not independent.

Search and databases: estimating the size of a query that matches any of several overlapping criteria, without listing every record.

Common Mistakes

Forgetting to add back the triple overlap. Stopping after subtracting the pairs undercounts, since people in all three groups have been removed entirely (3 − 3 = 0).

Using the formula with inconsistent overlap figures. The pairwise overlaps must include the people in all three groups, as "take both Maths and Physics" does here. If a figure means "both but not the third," the arithmetic changes.

Assuming events are independent to multiply overlaps. Setting P(A ∩ B) = P(A)P(B) is valid only if independence is known. See joint, marginal, and conditional probability for how to test that from a table.

Applying simple addition to overlapping events. Summing probabilities without subtracting overlaps can exceed 1, a warning sign that the events overlap.

Why do the signs alternate?

Each level corrects the previous level's overcount or undercount. Singles overcount overlaps, pairs subtract too much from triple overlaps, and triples restore them, and so on, until each element of the union is counted exactly once.

Does it work for more than three events?

Yes. For n events, add all singles, subtract all pairs, add all triples, and continue alternating up to the n-way intersection. The number of terms grows quickly, so it is typically used when a symmetry, like the hat problem, collapses each level to a simple formula.

How is it different from the complement rule?

The complement rule computes P(at least one) as 1 − P(none), which is easy when the chance of none can be found directly, such as with independence. Inclusion–exclusion works from the overlaps and does not need that.

Can I use it with conditional probabilities?

Yes, by converting to intersections first. Each intersection probability can be written with the multiplication rule, P(A ∩ B) = P(A) × P(B | A), as shown in probability trees.