When adding double-counts the overlap
Across this rung you have built a counting toolkit: the multiplication principle for stringing independent choices together, permutations for ordered arrangements, and the binomial coefficient for unordered selections. All of those answer "how many ways" by building things up. This last guide tackles the cases where building up fails — where the categories you are counting overlap, and a naive sum counts the overlap twice. The cure has a name: the inclusion-exclusion principle.
Picture a class of 30 students. Suppose 18 take Chinese and 15 take English. How many take at least one of the two? It is tempting to say 18 + 15 = 33 — but that is more than the whole class, so something is wrong. The students who take both languages were counted once inside the 18 and again inside the 15. If 9 students take both, then 18 + 15 counts those 9 twice, so we must subtract them back out: 18 + 15 - 9 = 24 students take at least one language. That single subtraction is inclusion-exclusion at its smallest.
Two-set inclusion-exclusion (sizes of sets): |A or B| = |A| + |B| - |A and B| Class example: |Chinese or English| = 18 + 15 - 9 = 24 Contrast: if A and B never overlap (mutually exclusive), |A and B| = 0, so |A or B| = |A| + |B| (the plain addition rule)
Why the addition rule needed a fix
Earlier in this rung the addition rule said: if a task can be done in one of several non-overlapping ways, add the counts. The crucial fine print is non-overlapping. When the categories are mutually exclusive — no item belongs to two of them at once — plain addition is exactly right, because nothing gets counted twice. Inclusion-exclusion is what you reach for the moment that assumption breaks and the categories share members.
There is also a deep tie to logic that explains the alternating signs to come. Saying "belongs to A or B" is the complement of "belongs to neither A nor B", and by De Morgan's laws the not-A-and-not-B side is built from intersections. So every union question can be re-read as a question about overlaps. Inclusion-exclusion is just the bookkeeping that keeps every overlap counted exactly once, no more and no less.
Three sets and the alternating pattern
With three overlapping sets the bookkeeping is richer, and walking through it reveals the general rule. Add the three single sizes, |A| + |B| + |C|. Now any item in two of the sets has been counted twice, so subtract each pairwise overlap: minus |A and B|, |A and C|, |B and C|. But what about an item sitting in all three? It was added three times, then subtracted three times (once in each pair) — leaving it counted zero times, which is too few. So we must add it back once. The signs alternate: plus singles, minus pairs, plus the triple.
Three-set inclusion-exclusion:
|A or B or C| = |A| + |B| + |C|
- |A&B| - |A&C| - |B&C|
+ |A&B&C|
General pattern (n sets):
add all single sizes, subtract all pairwise intersections,
add all triple intersections, subtract all quadruples, ...
(odd-sized intersections +, even-sized intersections -)The reason the alternating pattern is exactly right, and not just a lucky fix, is that it forces every element to be counted a net of one time. An element lying in exactly m of the sets gets added and subtracted across many terms, and those plus-and-minus contributions cancel down to precisely 1 for every m at least 1 — a small algebraic miracle that comes straight from the binomial coefficient identities you saw in guide 3. You do not need the proof to use the formula, but it is good to know the signs are forced, not chosen.
Counting the hard way: complement and a worked count
Inclusion-exclusion is often paired with its quiet partner, complementary counting: instead of counting what you want directly, count its opposite and subtract from the whole. This is the counting echo of the complement rule, P(not A) = 1 - P(A). When the thing you want is tangled but its negation is clean — "at least one" is messy, "none" is simple — flip the problem. The classic example is counting integers from 1 to 100 divisible by 2 or 3 or 5.
- Count multiples of each single number up to 100: of 2 there are 50, of 3 there are 33, of 5 there are 20. Sum: 50 + 33 + 20 = 103.
- Subtract the pairwise overlaps (multiples of the products): of 6 there are 16, of 10 there are 10, of 15 there are 6. Subtract 16 + 10 + 6 = 32, giving 103 - 32 = 71.
- Add back the triple overlap (multiples of 2*3*5 = 30): there are 3 of them. So 71 + 3 = 74 integers are divisible by 2, 3, or 5.
- If you instead wanted how many are divisible by none of them, complement: 100 - 74 = 26 integers from 1 to 100 are coprime to 30.
Notice how the two ideas braid together. We used inclusion-exclusion to count the union (divisible by 2, 3, or 5), then complementary counting to flip it into the "none" answer in one subtraction. A purely direct attack — listing every coprime integer — would be slow and error-prone; the structured plus-minus-plus made it mechanical. This is what "counting the hard way" really means: not harder arithmetic, but a method that survives overlaps a simple multiplication or combination cannot.
Derangements: the formula proving its worth
Here is where inclusion-exclusion stops being a tidy trick and earns real respect. A derangement is a permutation in which no item ends up in its own original spot. Picture n letters and n addressed envelopes, stuffed completely at random: a derangement is the disaster where not a single letter reaches the right envelope. Counting these directly is brutal, because forbidding one fixed point interacts with forbidding another. Inclusion-exclusion handles it cleanly by counting the bad permutations — those with at least one letter in the right place — and subtracting.
Let A_i be the set of permutations that fix item i in place. We want permutations in none of the A_i, so by complement we need n! minus the size of the union, and the union is exactly what inclusion-exclusion computes. The pairwise, triple, and higher overlaps collapse into a famous alternating sum, and the derangement count D(n) lands on a strikingly compact formula. Even more surprising: the fraction of all permutations that are derangements settles down near 1/e — about 0.3679 — almost immediately as n grows.
D(n) = n! * ( 1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n / n! ) Small values: D(1)=0 D(2)=1 D(3)=2 D(4)=9 D(5)=44 Limit: D(n) / n! -> 1/e ~ 0.3679 (already true to 3 digits by n=6)