Worked examples — Inclusion-exclusion principle

Before anything, one reminder of the only rule we use, in words:

---

The scenario matrix

Every inclusion–exclusion problem you will ever meet is one of these cells. The right column names the example that nails it.

#	Case class	What makes it tricky	Nailed by
C1	2 sets, generic overlap	remember to subtract once	Ex 1
C2	2 sets, disjoint ($A\cap B=\varnothing$)	overlap term is zero	Ex 2
C3	2 sets, one inside the other ($A\subseteq B$)	union collapses to the big set	Ex 2
C4	3 sets, full formula	the "+triple" restoration	Ex 3
C5	Complement trick ("none of them" / "at least one")	count the opposite, subtract from total	Ex 4
C6	Probability version (measures, not counts)	divide by universe / use $P$	Ex 5
C7	Degenerate: all sets equal	union = any one of them	Ex 6
C8	Limiting behaviour (derangement ratio as $n\to \infty$)	infinite sign-alternating sum	Ex 7
C9	Exam twist: "exactly $r$" not "at least one"	different coefficients	Ex 8
C10	4 sets, real-world word problem	four-way sign bookkeeping	Ex 9

---

Ex 1 — C1: two sets, generic overlap

Steps.

1. Name the sets. $A$ = French-studiers, $|A|=22$; $B$ = German, $|B|=17$; $|A\cap B|=9$. Why this step? Inclusion–exclusion needs the overlap size named explicitly — it's the whole point.
2. Add the singles: $|A|+|B|=22+17=39$. Why this step? This counts each "both" student twice, so it's too big.
3. Subtract the overlap once: $39-9=30$. Why this step? The $9$ both-students were counted twice; subtracting $9$ counts them once.

$|A\cup B|=22+17-9=30.$

Verify: partition into disjoint pieces — only French $=22-9=13$, only German $=17-9=8$, both $=9$. Sum $13+8+9=30$. ✓ And $30\le 40$, so it fits in the class. ✓

---

Ex 2 — C2 & C3: disjoint sets, and one set inside another

Steps for (a) — the disjoint case C2.

1. Disjoint means $A\cap B=\varnothing$, so $|A\cap B|=0$. Why this step? The general formula still applies — a zero overlap is just a special value.
2. $|A\cup B|=12+7-0=19$.

Verify (a): with no overlap there's nothing double-counted, so plain addition is already correct. $19$. ✓

Steps for (b) — the nested case C3.

1. $A\subseteq B$ means every chess-player is already in the games club, so $A\cap B=A$ and $|A\cap B|=|A|=8$. Why this step? The overlap is the smaller set when one set sits inside the other.
2. $|A\cup B|=|A|+|B|-|A\cap B|=8+20-8=20$.

Verify (b): the union is just the bigger set $B$, so it should equal $|B|=20$. ✓ The formula did not give the naive $28$ — because the $8$ chess players are not new people.

---

Ex 3 — C4: three sets, full formula (with figure)

Look at the figure: the centre region (all three) sits inside every pairwise lens.

Steps.

1. Add singles: $60+50+40=150$. Why this step? Anyone in two drinks counted twice; anyone in all three counted three times.
2. Subtract pairs: $-(30+20+15)=-65$, giving $150-65=85$. Why this step? This fixes the double-counted pair-only people, but over-erases the all-three group.
3. Track the all-three group of $10$: added $+3$ times in step 1, subtracted $-3$ times in step 2 → net $0$. That's wrong; we want $1$. Why this step? This is exactly why the $+$triple exists — see the dark centre in the figure.
4. Add back the triple: $85+10=95$.

$|T\cup C\cup J|=60+50+40-30-20-15+10=95.$

Verify: "none" $=100-95=5$. Also decompose into 7 disjoint Venn regions and sum: only-T $=60-30-20+10=20$, only-C $=50-30-15+10=15$, only-J $=40-20-15+10=15$, T∩C-only $=30-10=20$, T∩J-only $=20-10=10$, C∩J-only $=15-10=5$, all-three $=10$. Total $=20+15+15+20+10+5+10=95$. ✓

---

Ex 4 — C5: the complement trick ("at least one" via "none")

Why a new tool here: counting "divisible by $2$ or $3$ or $5$" directly is inclusion–exclusion — but this problem also teaches the complement idea used in Ex 7. We do it directly first.

Steps.

1. Singles — count multiples up to $100$. $\lfloor 100/2\rfloor =50$, $\lfloor 100/3\rfloor =33$, $\lfloor 100/5\rfloor =20$. Why this step? $\lfloor 100/d\rfloor$ = how many multiples of $d$ are $\le 100$ (every $d$-th number). $\lfloor x\rfloor$ means "==round $x$ down to a whole number=="
2. Pairs — divisible by both $a$ and $b$ means divisible by $\text{lcm}(a,b)$. $\text{lcm}(2,3)=6:\lfloor 100/6\rfloor =16$; $\text{lcm}(2,5)=10:\lfloor 100/10\rfloor =10$; $\text{lcm}(3,5)=15:\lfloor 100/15\rfloor =6$. Why this step? "divisible by 2 and 3" is the intersection, and lcm is the smallest number both divide.
3. Triple — $\text{lcm}(2,3,5)=30:\lfloor 100/30\rfloor =3$.
4. Assemble with alternating signs: $50+33+20-(16+10+6)+3=103-32+3=74.$

Verify (complement): count divisible by none of $2,3,5$ — i.e. coprime-ish survivors $=100-74=26$. Sanity: exactly divisible by none should be a handful of numbers like $1,7,11,13,\dots$; $26$ is plausible. Direct union $=74$. ✓

---

Ex 5 — C6: probability version

Why probability not counts: dividing every count by the universe size $52$ turns the same formula into probabilities — the additivity is identical.

Steps.

1. $P(A)=13/52=1/4$ (13 hearts). $P(B)=12/52=3/13$ (12 face cards). Why this step? Probability of an equally-likely event $=$ favourable $÷$ total.
2. Overlap: face-card hearts are J♥, Q♥, K♥, so $|A\cap B|=3$, $P(A\cap B)=3/52$. Why this step? $A\cap B$ = cards that are both heart and face.
3. Inclusion–exclusion for probability: $P(A\cup B)=\frac{13}{52}+\frac{12}{52}-\frac{3}{52}=\frac{22}{52}=\frac{11}{26}.$

Verify: count the union directly — hearts (13) plus non-heart face cards ($12-3=9$) $=22$ cards, $22/52=11/26\approx 0.423$. Bigger than $1/4$ as expected (we added face cards). ✓ It's a valid probability, $0\le 11/26\le 1$. ✓

---

Ex 6 — C7: the fully degenerate case (all sets equal)

Steps.

1. Every set has $5$ elements, and every intersection (pair or triple) is also the whole set, size $5$. Why this step? When sets coincide, all overlaps collapse to that one set.
2. Apply the 3-set formula: $|A\cup B\cup C|=\underset{15}{\underbrace{(5+5+5)}}-\underset{15}{\underbrace{(5+5+5)}}+\underset{5}{\underbrace{5}}=5.$

Verify: the union of three identical sets is just that set, size $5$. The formula gives $15-15+5=5$. ✓ This is the general "element in $m=3$ sets counted exactly once" identity in action: $\left(\genfrac{}{}{0ex}{}{3}{1}\right)-\left(\genfrac{}{}{0ex}{}{3}{2}\right)+\left(\genfrac{}{}{0ex}{}{3}{3}\right)=3-3+1=1$, so each of the $5$ elements nets $1$. ✓

---

Ex 7 — C8: limiting behaviour (derangements as $n\to \infty$)

Why inclusion–exclusion: "at least one letter correct" is a union of events "letter $i$ correct"; the complement is "none correct".

Steps.

1. Let $A_i$ = permutations fixing position $i$. $|A_i|=(n-1)!$, a $k$-fold intersection fixes $k$ chosen spots: $(n-k)!$, chosen $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ ways. Why this step? Fixing $k$ letters correctly leaves $(n-k)!$ arrangements of the rest.
2. "At least one fixed" $={\sum }_{k=1}^n(-1{)}^{k+1}(\genfrac{}{}{0ex}{}{n}{k})(n-k)!$. Subtract from $n!$ to get "none fixed": $D_n={\sum }_{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})(n-k)!=n!{\sum }_{k=0}^n\frac{(-1{)}^k}{k!}.$ Why this step? $\left(\genfrac{}{}{0ex}{}{n}{k}\right)(n-k)!=n!/k!$, pulling out $n!$.
3. For $n=4$: $D_4=24\left(1-1+\frac{1}{2}-\frac{1}{6}+\frac{1}{24}\right)=24\cdot \frac{9}{24}=9$. Probability $=9/24=3/8=0.375$.
4. Limit: ${\sum }_{k=0}^{\infty }\frac{(-1{)}^k}{k!}=e^{-1}$ (the exponential series at $-1$). So $D_n/n!\to e^{-1}\approx 0.3679$. Why this step? $e^x=\sum x^k/k!$ evaluated at $x=-1$; the sign-alternating I–E terms are exactly this series.

Verify: $D_4=9$ (matches parent note). $9/24=0.375$, and $e^{-1}=0.367879\dots$ — already very close at $n=4$. ✓ The "no match" chance does not vanish; it settles near $37\%$.

---

Ex 8 — C9: the exam twist ("exactly one", not "at least one")

Why different coefficients: "exactly one" needs a formula that cancels out multi-membership, giving different multipliers than the union.

Steps.

1. Use the disjoint-region decomposition from Ex 3's Verify: only-T $=20$, only-C $=15$, only-J $=15$. Why this step? "Exactly one drink" = sum of the three single-only regions.
2. Add them: $20+15+15=50$.
3. Cross-check with the coefficient formula: $\text{exactly one}=\sum |A_i|-2\sum |A_i\cap A_j|+3|A\cap B\cap C|.$ $=150-2(65)+3(10)=150-130+30=50.$ Why this step? An element in exactly $2$ sets must net $0$: $2-2\cdot 1=0$; in all $3$: $3-2\cdot 3+3=0$. Only single-membership survives with coefficient $1$.

Verify: both methods give $50$. Also: exactly-two total $=20+10+5=35$, exactly-three $=10$, none $=5$; $50+35+10+5=100$. ✓

---

Ex 9 — C10: four sets, real-world word problem

Steps.

1. Add singles ($+$): $30+25+18+12=85$. Why this step? $k=1$, sign $(-1{)}^2=+$.
2. Subtract all $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ pairs ($-$): $15+10+6+8+5+4=48$, giving $85-48=37$. Why this step? $k=2$, sign $-$; fixes double-counting.
3. Add all $\left(\genfrac{}{}{0ex}{}{4}{3}\right)=4$ triples ($+$): $5+3+2+2=12$, giving $37+12=49$. Why this step? $k=3$, sign $+$; restores triple-erased people.
4. Subtract the single quadruple ($-$): $49-1=48$. Why this step? $k=4$, sign $-$; the all-four person was over-added by the triples.

$|Y\cup J\cup C\cup R|=85-48+12-1=48.$

Verify: answer $48\le 50$ team size, so $2$ people know none — plausible. Track the all-four person: added $\left(\genfrac{}{}{0ex}{}{4}{1}\right)=4$ (singles) $-\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ (pairs) $+\left(\genfrac{}{}{0ex}{}{4}{3}\right)=4$ (triples) $-\left(\genfrac{}{}{0ex}{}{4}{4}\right)=1$ (quad) $=4-6+4-1=1$. Counted exactly once. ✓

---

Recall Which cell was which?

C1 generic 2-set (Ex1) ::: subtract the overlap once C2 disjoint / C3 nested (Ex2) ::: overlap is $0$ or is the smaller set C4 three sets (Ex3) ::: add the triple back C5 complement (Ex4) ::: "none" $=$ total $-$ union C6 probability (Ex5) ::: same formula with $P$ C7 all equal (Ex6) ::: union $=$ any one set C8 limit (Ex7) ::: $D_n/n!\to e^{-1}$ C9 exactly-one (Ex8) ::: coefficients $1,-2,+3$ C10 four sets (Ex9) ::: signs $+,-,+,-$

---

Connections

• Inclusion-exclusion principle — the parent: the formula these examples exercise
• Set Theory & Venn Diagrams — the disjoint-region decomposition used in Ex 3 & 8
• Counting Principles & Combinatorics — $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ counts of intersections in Ex 7 & 9
• Probability Axioms — Ex 5's probability form is additivity plus overlap correction
• Derangements & Permutations — Ex 7 is the classic derangement payoff
• Binomial Theorem — $\sum (-1{)}^k/k!\to e^{-1}$ limit in Ex 7
• Bonferroni Inequalities — truncating these alternating sums gives bounds