Inclusion–Exclusion

Correcting for overlaps

An interactive lesson with 8 steps, about 7 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• $|A \cup B| = |A| + |B| - |A \cap B|$; with more sets, signs alternate.
• Derangements: $D(n) = n!\sum_k (-1)^k/k!$.
• The chance of a derangement approaches $1/e \approx 37\%$.

Steps

1. Don’t count twice
2. Two or three
3. Three sets
4. Two, three or five
5. Secret Santa
6. Four friends
7. Approaching 1/e
8. Somebody gets their own