Inclusion-Exclusion

Medium2–3 hrsInclusion-ExclusionDerangementsAt Least One

Overview

Inclusion-exclusion formalizes the rule: when you add two overlapping sets, you count the overlap twice. So subtract it once. If three sets overlap, you subtracted the triple overlap too many times, so add it back. The pattern alternates. In practice, 'at least one' is the most frequent application — and the complement trick is almost always easier.

How to Recognize

→'At least one of A, B, C…' — flip to P(none) via complement
→Counting arrangements with restrictions (no two elements adjacent)
→Overlapping event sets where simple addition overcounts

Step-by-Step Approach

1.For 'at least one': P(≥1) = 1 − P(none) — almost always the best approach
2.|A∪B| = |A| + |B| − |A∩B| (subtract the overlap you double-counted)
3.|A∪B∪C| = |A|+|B|+|C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|
4.Derangements (no fixed points): D(n) = n!·Σ(−1)^k/k! ≈ n!/e

Key Formulas

|A_1 \cup \cdots \cup A_n| = \sum|A_i| - \sum|A_i\cap A_j| + \sum|A_i\cap A_j \cap A_k| - \cdots

02Derangements:

D(n) = n!\sum_{k=0}^n \frac{(-1)^k}{k!} \approx \frac{n!}{e}

P(\text{at least one ace in 5 cards}) = 1 - \frac{\binom{48}{5}}{\binom{52}{5}} \approx 34.1\%

Worked Examples

0Quick Example

P(at least one 6 in three dice rolls) = 1 − (5/6)³ = 91/216 ≈ 42.1%.

Problem

What is P(at least one pair) in a 5-card hand? (A pair means at least 2 cards of the same rank.)

Solution

P(at least one pair) = 1 − P(no pair) = 1 − P(all 5 ranks different).

P(all different ranks): choose 5 ranks from 13: C(13,5). Choose one suit for each: 4⁵.

P(no pair) = C(13,5)·4⁵ / C(52,5) = 1287·1024 / 2598960 = 1317888/2598960 ≈ 50.7%.

P(at least one pair) = 1 − 0.507 = 49.3%.

Answer

$P(\text{at least one pair}) \approx 49.3\%$ . The complement of 'all ranks different' is easier than summing over all possible pair/two-pair/etc. cases.

Common Mistakes

!
Forgetting to add back the triple intersection after subtracting all pairwise intersections.
!
Using inclusion-exclusion when complement is simpler. For 'at least one' with independent events, P(none) = Π(1−pᵢ) is faster.
!
Derangements: confusing D(n)/n! with the reciprocal. P(derangement) ≈ 1/e, not 1−1/e.

Practice Problems

Click "Show Answer" to reveal

Four letters are randomly placed in four envelopes. P(at least one letter is in the correct envelope)?

Hint: Complement: P(all wrong) = P(derangement with n=4).

What is the probability that a random permutation of {1,2,3,4,5} has at least one element in its correct position (i is in position i)?

Hint: Complement: P(no fixed point) = P(derangement).

In a group of 30 people, what is P(at least two people share a birthday)? Use the approximation.

Hint: P(no collision) ≈ e^(−k(k−1)/(2·365)) with k=30.

Back to Study Plan

Birthday & Coupon Collector Markov Chains & Absorbing States