Principle of Inclusion–Exclusion
When you count how many people study Maths or Physics, you can't just add, those who study both get counted twice. The Principle of Inclusion–Exclusion is the systematic fix: add individual sets, subtract pairwise overlaps, add back triple overlaps, and so on. It's the engine behind Venn diagrams and a surprisingly powerful combinatorial tool.
In a class of 30 students, 18 study Maths and 15 study Physics. Without using any formulado you think it's possible that all 15 Physics students also study Maths? Is it possible that none of them do? If you're told exactly 8 study both, how many study at least one subject? Write your reasoning.
Every inclusion–exclusion problem asks you to do one of two things: find the union given the individual sets and their overlaps, or find an intersection or missing piece given the union and other information.
The entire lesson turns on one idea: when you add two sets, you double-count their overlap. So you subtract it once. For three sets, you over-subtract the triple overlap, so you add it back. The formula alternates: add singles, subtract pairs, add triples, subtract quadruples, and so on.
Key facts
- $|A \cup B| = |A| + |B| - |A \cap B|$
- $|A \cup B \cup C| = |A|+|B|+|C| - |A\cap B| - |B\cap C| - |A\cap C| + |A\cap B\cap C|$
- Union = OR; intersection = AND; neither = outside all sets
Concepts
- Why adding two sets double-counts the intersection
- Why the triple intersection is subtracted once too many in the three-set formula and must be added back
- How Venn diagrams make inclusion–exclusion calculations visual and error-free
Skills
- Apply the two-set formula to solve word problems
- Apply the three-set formula with all pairwise and triple intersections
- Draw and label Venn diagrams to verify results
Suppose you want to count how many elements are in $A$ or $B$ (at least one of the two sets). If you simply add $|A| + |B|$, every element in both sets gets counted twice. So you subtract the overlap once:
Rearranging, you can also find the intersection if you know the union: $|A \cap B| = |A| + |B| - |A \cup B|$. And the number in neither set is $|U| - |A \cup B|$.
The overlap region $A \cap B$ is subtracted once so it is counted exactly once in the union.
|A B| = |A| + |B| - |A B|. Always subtract the intersection.; Rearrangement: |A B| = |A| + |B| - |A B| (find overlap if you know the rest)
Pause, copy the two-set inclusion-exclusion formula into your book: $|A \cup B| = |A| + |B| - |A \cap B|$; rearrangement: $|A \cap B| = |A| + |B| - |A \cup B|$.
Quick check: In a class of 30 students, 18 study Maths, 15 study Physics, and 8 study both. How many study at least one of these subjects?
We just saw that $|A \cup B| = |A| + |B| - |A \cap B|$ corrects for the double-counting of elements in both sets. That raises a question: when three sets overlap, elements in all three are counted in three different pairwise intersections, how does inclusion-exclusion extend to remove all excess counting? This card answers it → $|A \cup B \cup C| = |A|+|B|+|C| - |A \cap B| - |B \cap C| - |A \cap C| + |A \cap B \cap C|$.
For three overlapping sets, the double-counting problem is more complex. Each element in exactly two sets gets counted twice (once for each set it belongs to); each element in all three sets gets counted three times. Applying inclusion–exclusion carefully:
Why add back $|A \cap B \cap C|$? When you subtract the three pairwise intersections, you subtract the triple intersection three times, once in each pairwise term. But it should only be subtracted twice (since it was added three times). Net: subtract $3 - 3 + 1 = 1$ time total. The triple intersection ends up counted exactly once. ✓
Memory aid: singles (add), pairs (subtract), triple (add). Alternating signs, starting positive.
|A B C| = |A|+|B|+|C| - |A B| - |B C| - |A C| + |A B C|; Each element in exactly one set is counted 1-0+0=1 ✓
Pause, copy the three-set inclusion-exclusion formula into your book: $|A \cup B \cup C| = |A|+|B|+|C| - |A \cap B| - |B \cap C| - |A \cap C| + |A \cap B \cap C|$.
Did you get this? True or false: in the three-set inclusion–exclusion formula, $|A \cap B \cap C|$ is added (not subtracted).
Worked examples · 3 in a row, reveal as you go
In a class of 30 students, 18 study Maths ($M$), 15 study Physics ($P$), and 8 study both. How many study at least one of these subjects? How many study neither?
In a survey, 40 people like tea, 35 like coffee, and 55 like at least one of the two. How many like both? How many like neither if the survey had 60 people?
Find $|A \cup B \cup C|$ if $|A|=20$, $|B|=25$, $|C|=18$, $|A \cap B|=8$, $|B \cap C|=6$, $|A \cap C|=5$, $|A \cap B \cap C|=2$.
Fill the gap: If $|A|=30$, $|B|=40$, and $|A\cap B|=12$, then $|A\cup B| = $ .
Misconceptions to fix · the 3 traps that cost marks
Did you get this? True or false: for three sets, the number of elements in at least one set equals $|A|+|B|+|C|-|A\cap B|-|B\cap C|-|A\cap C|$ (with no other correction needed).
Activities · practice with the ideas
In a survey, 40 people like tea, 35 like coffee, and 20 like both. How many like at least one? How many like neither if 60 were surveyed?
In a group of 50 people, 30 speak French and 25 speak Spanish. If 45 speak at least one language, how many speak both?
Find $|A \cup B \cup C|$ if $|A|=20$, $|B|=25$, $|C|=18$, $|A \cap B|=8$, $|B \cap C|=6$, $|A \cap C|=5$, $|A \cap B \cap C|=2$.
How many integers from 1 to 100 are divisible by 2 or 3? (Hint: $|A| = \lfloor 100/2 \rfloor$, $|B| = \lfloor 100/3 \rfloor$, $|A\cap B| = \lfloor 100/6 \rfloor$.)
Explain why the formula for $|A \cup B \cup C|$ has a positive $|A \cap B \cap C|$ term. What would go wrong if you omitted it?
Odd one out: Which statement about the three-set inclusion–exclusion formula is NOT correct?
Earlier you were asked: if 18 study Maths, 15 study Physics, and 8 study both, how many study at least one?
$|M \cup P| = 18 + 15 - 8 = 25$ students study at least one subject. This is why you can't just add 18 and 15: the 8 students who study both would be counted twice, giving the wrong answer of 33.
Both students in the hook were partially right: at least $18+15-30=3$ study both (if all 30 study at least one) and at most $\min(18,15)=15$ study both. Since exactly 8 study both, the union is exactly 25.
Pick your answer, then rate your confidencethat tells the system what to drill next. Each retry pulls a fresh mix from the bank.
Q1. In a survey, 40 people like tea, 35 like coffee, and 20 like both. How many like at least one? (2 marks)
Q2. Find $|A \cup B \cup C|$ if $|A|=20$, $|B|=25$, $|C|=18$, $|A \cap B|=8$, $|B \cap C|=6$, $|A \cap C|=5$, $|A \cap B \cap C|=2$. (3 marks)
Q3. How many integers from 1 to 120 are divisible by 2 or 3 or 5? Use inclusion–exclusion. Let $A$, $B$, $C$ be the sets of multiples of 2, 3, 5 respectively. (3 marks)
Comprehensive answers (click to reveal)
Activities: 1. $40+35-20=55$; neither $=60-55=5$ · 2. $|F\cap S|=30+25-45=10$ · 3. $20+25+18-8-6-5+2=46$ · 4. $50+33-16=67$ · 5. Without $+|A\cap B\cap C|$, the triple overlap is subtracted three times instead of two, so elements in all three sets are counted zero times instead of one, the union is under-counted by $|A\cap B\cap C|$.
Q1 (2 marks): $|T\cup C|=40+35-20=55$ [2].
Q2 (3 marks): Singles $=63$; pairs $=8+6+5=19$; triple $=2$. $|A\cup B\cup C|=63-19+2=46$ [3].
Q3 (3 marks): $|A|=60$, $|B|=40$, $|C|=24$ [0.5]. $|A\cap B|=20$, $|A\cap C|=12$, $|B\cap C|=8$ [1]. $|A\cap B\cap C|=4$ [0.5]. $|A\cup B\cup C|=60+40+24-20-12-8+4=88$ [1].
Five timed questions drawn from the Module 4 bank. Beat the boss to bank a tier, gold (90% + speed), silver (75%), or bronze (50%). Replays welcome.
⚔ Enter the arenaClimb platforms by answering Combinatorics questions. Lighter alternative to the boss.
Mark lesson as complete
Tick when you've finished the practice and review.