The idea: count every element exactly once
To count the elements of a union A ∪ B ∪ C, it is tempting to add the sizes |A| + |B| + |C|. That counts an element once for every set it belongs to. An element in two sets is counted twice, and one in all three is counted three times. Inclusion–exclusion fixes this with alternating corrections: subtract the pairwise intersections, then add back the triple intersection. The canvas keeps a tally in every region of the Venn diagram: how many times the terms applied so far have counted that region. The goal is ×1 everywhere.
Press Next Step to apply one term. The touched regions blink and change colour: white ×0, green ×1, orange ×2, red ×3 or more, purple for a negative tally. The right panel lists the terms and the running total.
Two sets
For two sets the formula is |A ∪ B| = |A| + |B| − |A ∩ B|. Take the numbers 1 to 100, A = multiples of 2 and B = multiples of 3. Then |A| = 50 and |B| = 33. The multiples of 6 (6, 12, 18, …) are in both, so 50 + 33 = 83 counts them twice. Subtracting |A ∩ B| = 16 leaves 67 numbers divisible by 2 or 3, and 33 divisible by neither (Demo: two sets). The small numbers in brackets on the canvas are the true sizes of the regions: 34 only in A, 17 only in B, 16 in both.
Three sets: watch the tallies
With three sets there are 7 regions inside the union. After |A| + |B| + |C| the three outer parts show ×1, the three lenses ×2 and the centre ×3. Subtracting |A ∩ B|, |A ∩ C| and |B ∩ C| takes one tally from each region inside that pair. The lenses drop to ×1, but the centre is inside all three pairs, so it drops to ×0. Adding |A ∩ B ∩ C| puts it back to ×1 (Demo: three sets):
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|
In general, with n sets, add all single sets, subtract all pairs, add all triples, subtract all quadruples, and so on, with the sign (−1)k+1 for intersections of k sets. Why this always works: an element that lies in exactly k of the sets is counted C(k,1) − C(k,2) + C(k,3) − … times. By the binomial theorem, (1 − 1)k = 0 = 1 − C(k,1) + C(k,2) − …, so that sum is exactly 1. See Pascal's Triangle for the binomial coefficients and Truth Tables and Sets for how the regions of a Venn diagram line up with the rows of a truth table.
Worked example: 1..100 divisible by 2, 3 or 5
Let A, B, C be the multiples of 2, 3 and 5 in 1..100. A number is in A ∩ B when it is divisible by 2 and by 3, which means by 6 (the least common multiple). The number of multiples of d up to 100 is ⌊100/d⌋ (Demo: 1..100 divisible by 2, 3 or 5).
| term | multiples of | count | running total |
|---|---|---|---|
| + |A| | 2 | 50 | 50 |
| + |B| | 3 | 33 | 83 |
| + |C| | 5 | 20 | 103 |
| − |A ∩ B| | 6 | 16 | 87 |
| − |A ∩ C| | 10 | 10 | 77 |
| − |B ∩ C| | 15 | 6 | 71 |
| + |A ∩ B ∩ C| | 30 | 3 | 74 |
So 74 numbers are divisible by 2, 3 or 5, and 100 − 74 = 26 by none of them (1, 7, 11, 13, 17, 19, 23, 29, 31, …). The running total passes 100 after the third term: proof that it over-counts. The check line under the terms multiplies each region's size by its tally. It always equals the running total, which is the whole reason the method works.
Derangements: counting what is in none of the sets
Often the useful number is the complement: the elements in none of the sets, |U| − |A₁ ∪ … ∪ Aₙ|. A derangement is a permutation that moves every element, such as letters put back in the wrong envelopes. For 1234, let Aᵢ be the permutations that keep i in place. Fixing i leaves 3! orders of the rest; fixing a pair leaves 2!, and so on. There are C(4,k) ways to choose which k positions are fixed:
|A₁ ∪ A₂ ∪ A₃ ∪ A₄| = 4·3! − 6·2! + 4·1! − 1·0! = 24 − 12 + 4 − 1 = 15, so D₄ = 4! − 15 = 9.
The canvas shows all 24 permutations with their tallies (Demo: derangements of 4). A permutation with f fixed points gets f from the first term, then loses C(f,2), gains C(f,3) and so on. The identity 1234 fixes all four, so its tally goes 4, −2, 2, 1: tallies can go negative on the way. At the end every permutation that fixes something shows ×1 and the 9 derangements, such as 2143, 3412 and 4321, show ×0. In general Dn = n! (1 − 1/1! + 1/2! − … ± 1/n!), which is close to n!/e, so about 37% of random permutations fix nothing. For more on counting arrangements see Permutations.
The pigeonhole principle
The pigeonhole principle says: if n items go into m boxes and n > m, some box gets at least two. The proof is the best case. Put the pigeons one per box to keep them apart; after m pigeons every box is full and the next one must share (Demo: pigeonhole). The general form: some box gets at least ⌈n/m⌉ items, because if every box had fewer, the total would be at most m(⌈n/m⌉ − 1) < n.
It proves existence without saying which box. In any group of 367 people two share a birthday, since there are only 366 possible dates (with February 29). Among any 13 people two were born in the same month. Among any 5 points in a unit square two are at most √2/2 apart (cut the square into 4 small squares). The principle is also why a hash table with more keys than buckets must have a collision.
366 people guarantee a shared birthday, but a match is already 50% likely with 23: see the birthday paradox.
See The Pigeonhole Principle for socks, ⌈n/m⌉, sums divisible by n and the Erdős–Szekeres theorem, step by step.
What the page leaves out
The general n-set proof written out, the weighted (measure and probability) version P(A ∪ B) = P(A) + P(B) − P(A ∩ B), Möbius inversion, Euler's totient φ(n) by inclusion–exclusion over prime factors, Bonferroni inequalities (stopping early gives an upper or lower bound), and stronger pigeonhole results such as Ramsey theory. The birthday paradox (23 people give a better than even chance of a shared birthday) is a probability question, not a pigeonhole one.