8.5 Complements, inclusion-exclusion

“At least one” can be awkward to count directly. “None” is often much simpler. Likewise, adding the sizes or chances of overlapping sets counts some outcomes more than once. Complements and the principle of inclusion-exclusion (PIE) solve these two common paper-question patterns.

This is foundational to intermediate probability. Learn the addition rule, then practise three-set Venn diagrams. MIT's counting notes derive the three-set PIE formula.

A basic idea: count what is easier

For an event $A$, the complement $A^c$ contains every outcome where $A$ does not happen. Together, $A$ and $A^c$ exhaust the sample space. For events $A$ and $B$, the intersection $A\cap B$ is the overlap; the union $A\cup B$ contains every outcome in $A$, in $B$, or in both.

A complement is especially useful when the event we want has many ways to happen, but its opposite has only one or a few. For example, “at least one head in three coin tosses” covers seven different toss sequences. Its complement, “no heads,” is just $TTT$. Three independent fair tosses give $P(TTT)=(1/2)^3=1/8$, so the chance of at least one head is $1-1/8=7/8$. We replaced seven cases with one easier case. The two events cover every outcome without overlap, which is why subtracting from $1$ works.

A quick tour of formulas

$$P(A^c)=1-P(A),\qquad P(A\cup B)=P(A)+P(B)-P(A\cap B).$$

If $A$ and $B$ are disjoint, $A\cap B$ is empty, so $P(A\cap B)=0$. For example, if 18 students join one club, 15 join another, and 7 join both, then $18+15-7=26$ join at least one.

For $n$ independent identical trials, with success probability $p$, the probability of at least one success is $1-(1-p)^n$. Independence is needed for the power $(1-p)^n$.

Three overlapping sets

With three sets, add the three single-set totals, subtract the three pairwise overlaps, then add the three-way overlap back:

$$\begin{aligned} |A\cup B\cup C| ={}&|A|+|B|+|C|\\ &-|A\cap B|-|A\cap C|-|B\cap C|\\ &+|A\cap B\cap C|. \end{aligned}$$

The centre belongs to all three single sets, so the first line counts it three times. It also belongs to all three pairwise intersections, so the second line removes it three times. Without the final addition, it would be counted zero times. The same formula works with probabilities in place of set sizes.

The animation uses 40 students in three clubs. Use Next to fill the seven regions inside the circles, then watch PIE recover the same union by adding, subtracting, and restoring the centre.

How to approach a three-set question

1. Name the universe and the sets. Decide whether “both $A$ and $B$” includes members of $C$; unless the question says “exactly $A$ and $B$,” it does.
2. Fill the centre first. Put $|A\cap B\cap C|$ in the three-way overlap.
3. Fill each pair-only region. Subtract the centre from the corresponding pairwise intersection.
4. Fill the single-only regions. Subtract the pair-only regions and the centre from each set total. A negative region signals inconsistent data or a counting mistake.
5. Check the answer two ways. Add the seven regions inside the circles, then apply PIE. If the universe size is known, subtract the union to find how many are in none of the sets.

Application 1: three overlapping clubs

In a class of 40 students, club $A$ has 14 members, club $B$ has 14, and club $C$ has 12. The pairwise intersections have $|A\cap B|=4$, $|A\cap C|=3$, and $|B\cap C|=5$ members; one student is in all three. How many students are in at least one club, and how many are in none?

1. Fill the centre and pair-only regions. The centre is $1$. The pair-only counts are $4-1=3$, $3-1=2$, and $5-1=4$.
2. Fill the single-only regions. They are $14-(3+2+1)=8$ in $A$ only, $14-(3+4+1)=6$ in $B$ only, and $12-(2+4+1)=5$ in $C$ only.
3. Count the union. The seven regions sum to $8+6+5+3+2+4+1=29$. PIE checks this: $14+14+12-4-3-5+1=29$.
4. Count the outside. Of 40 students, $40-29=11$ belong to none of the clubs.

If a student is chosen uniformly from the class, the chance that they belong to at least one club is $29/40=0.725$.

Application 2: at least one six

You roll a fair die four independent times. What is the probability of seeing at least one six?

1. The complement is “no six on any roll.”
2. Each roll has chance $5/6$ of no six; independence gives $(5/6)^4=625/1296$.
3. The requested probability is $1-625/1296=671/1296\approx0.518$.

The complement saves you from separately counting exactly one, two, three, and four sixes.