Inclusion-Exclusion Principle

Hard4–5 hrsInclusion-ExclusionSieveDerangementsOvercounting

Overview

Inclusion-exclusion is the universal overcounting correction. When you sum sizes of sets A₁,...,Aₙ, you double-count intersections. Subtract pairwise intersections, then add back triple intersections, etc. The alternating sum converges to the exact union. This principle is behind derangement counting, surjection counting, Euler's totient function, the sieve of Eratosthenes, and many probability calculations. In trading: useful for computing P(at least one event triggers) when events are correlated.

How to Recognize

→'At least one of the following properties...'
→'None of the following properties...'
→Counting with overlapping forbidden sets
→Derangements, surjections, problems with 'no fixed points'
→Probability that at least one of n events occurs

Step-by-Step Approach

1.|A₁ ∪ A₂ ∪ ... ∪ Aₙ| = Σ|Aᵢ| - Σ|Aᵢ∩Aⱼ| + Σ|Aᵢ∩Aⱼ∩Aₖ| - ... ± |A₁∩...∩Aₙ|
2.For 'none' (complement): |neither| = |total| - |at least one|
3.By symmetry, often |Aᵢ| = same for all i, |Aᵢ∩Aⱼ| = same, etc.
4.Count the number of sets at each level: C(n,1), C(n,2), ...
5.Stop early if terms become negligible (alternating series often converges fast)

Key Formulas

|\bigcup_{i=1}^n A_i| = \sum_{k=1}^n (-1)^{k+1} \sum_{|S|=k} |\bigcap_{i\in S} A_i|

P(\text{derangement}) = \sum_{k=0}^n \frac{(-1)^k}{k!} \to e^{-1}

\text{Surjections from }n\text{ to }k: k!S(n,k) = \sum_{j=0}^k (-1)^j\binom{k}{j}(k-j)^n

P(\text{none of }n\text{ events}) \ge 1 - \sum_i P(A_i)

(Boole's inequality)

Worked Examples

0Quick Example

P(no ace in 5 cards from 52-card deck): total = C(52,5). At least one ace: C(4,1)C(48,4) - C(4,2)C(48,3) + C(4,3)C(48,2) - C(4,4)C(48,1). P(no ace) = 1 - P(at least one ace) ≈ 65.9%.

Problem

How many functions f: {1,2,3,4} → {1,2,3} are surjective (every element of {1,2,3} is hit)?

Solution

Total functions: 3⁴ = 81.

Let Aᵢ = functions missing value i. |A₁| = |A₂| = |A₃| = 2⁴ = 16 (map to {2,3} only, etc.).

|Aᵢ ∩ Aⱼ| = 1⁴ = 1 (map to only one value). 3 such pairs.

|A₁ ∩ A₂ ∩ A₃| = 0 (can't map to nothing).

|A₁ ∪ A₂ ∪ A₃| = 3(16) - 3(1) + 0 = 48 - 3 = 45.

Surjections = 81 - 45 = 36.

Answer

36 surjective functions. Verify: Stirling number S(4,3) = 6. Surjections = 3! × S(4,3) = 6×6 = 36. ✓

Common Mistakes

!
Stopping after the first term. |A₁ ∪ ... ∪ Aₙ| ≠ Σ|Aᵢ| — you must subtract intersections.
!
Confusing 'at least one' with 'exactly one.' P(exactly one) = Σ P(Aᵢ) - 2Σ P(Aᵢ∩Aⱼ) + 3Σ P(Aᵢ∩Aⱼ∩Aₖ) - ... (different formula).
!
In symmetric cases, forgetting to multiply by the number of sets: C(n,k) × |intersection of any k sets|.

Practice Problems

Click "Show Answer" to reveal

A room has 5 people. Each person independently sends a message to one of the other 4 people uniformly at random. What is P(at least one person receives no messages)?

Hint: Let Aᵢ = event person i receives no messages. |A₁ ∪ ... ∪ A₅| by inclusion-exclusion. P(person i receives nothing) = (3/4)^5 since each of the 4 senders avoids i with prob 3/4.

Back to Study Plan

Stars & Bars / Integer Partitions Permutation Statistics: Records & Fixed Points