Inclusion-Exclusion Principle

Context: FIT1058_MOC · the size (or probability) of a union of overlapping sets · alternating signed sum of all intersections · generalises $|A\cup B|=|A|+|B|-|A\cap B|$ · proved by Mathematical Induction

Quick Revision

• 🎯 Objective: size of a union of overlapping sets ➔ alternating signed sum of all intersections.
• 📦 Core Components: add singles ➔ subtract pairs ➔ add triples ➔ sign $(-1{)}^{k+1}$.
• ⚡ Key Constraint: $2^n-1$ terms (exponential); disjoint case collapses to addition.

📝 Core

1. The Correction (Overlap)

• Problem ➔ adding sizes overcounts shared elements.
• Two/three sets ➔ $|A\cup B|=|A|+|B|-|A\cap B|$; add back $|A\cap B\cap C|$ for three.
• Sign ➔ $k$-fold intersection carries $(-1{)}^{k+1}$ (+ odd, − even).

2. General Theorem

• Formula ➔ $|\bigcup A_i|={\sum }_{k=1}^n(-1{)}^{k+1}(\text{sum of }k\text{-fold intersection sizes})$.
• Each element once ➔ signs make every element counted exactly once.

3. Probability Version

• Same identity ➔ for probabilities of events.
• Counting = uniform case ➔ divide sizes by $|U|$ (Equally Likely Outcomes).

⚖️ Core Decision Matrix

$k$	Sign	Term
1	$+$	single-set sizes
2	$-$	pairwise intersections
3	$+$	triple intersections
all disjoint	—	collapses to $\sum |A_i|$ (Addition Principle)

When It Flips: the disjoint case (all intersections empty) is the Addition Principle. A dual form expresses $|\bigcap A_i|$ via union sizes (De Morgan). $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ counts the $k$-fold terms at each level.

📊 Exam Execution Trace

Manual Execution Trace

Divisible by 2, 3, or 5 among 100:

Step / State	$k$	Sign	Sum of sizes	Contribution
0 (Init)	—	—	—	—
1	1	$+$	$50+33+20$	$+103$
2	2	$-$	$16+10+6$	$-32$
3	3	$+$	$3$	$+3$

⚠️ Common Mistakes

• 💡 $2^n-1$ terms ➔ one per non-empty subset (Power Set count) — exact but exponential; practical only for small $n$ or when most intersections vanish.

🧠 Active Recall

State inclusion–exclusion for three sets and why each sign is needed.

• Hint: Count each element once.

Answer

• Short answer: $|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$.
• Why: Overcount fix ➔ triples counted 3×, dropped to 0 by pairwise subtraction, restored to 1 by the triple term.

Outline the inductive step of the general theorem.

• Hint: Two-set rule + distributive law.

Answer

• Short answer: Split off $A_{n+1}$, apply two-set rule, distribute the intersection, apply the hypothesis to both $n$-fold unions.
• Why: Reindex ➔ terms excluding and including $A_{n+1}$ combine into the full signed sum over $n+1$ sets.