1
Adding sizes over-counts overlaps
An element in two sets is counted twice, one in three is counted three times. Subtracting pairwise intersections over-corrects the triples, so they are added back.
Lesson · Combinatorics and Counting · Corrections
The Inclusion-Exclusion Principle
When sets overlap the sum rule over-counts. Inclusion and exclusion corrects it exactly, with alternating signs, and it is the tool behind derangements, surjection counts and Euler's totient function.
|A ∪ B| = |A| + |B| − |A ∩ B|
|A∪B∪C| = Σ|Aᵢ| − Σ|Aᵢ∩Aⱼ| + |A∩B∩C|
general: alternating sum over all nonempty subsets of the index set
usually applied to the COMPLEMENT: none of the properties
Correcting the over-count
Core ideas
What this lesson establishes
Each element must be counted exactly once. The alternating signs are what makes that happen for every element regardless of how many sets it lies in.
2
The signs are forced
An element in exactly m of the sets is counted C(m,1) − C(m,2) + C(m,3) − ⋯, which is 1 for every m ≥ 1 by the alternating-sum identity of “Binomial Coefficients and Pascal's Triangle”.
3
The complement form is usually what you want
"None of the properties" equals the total minus the union, and that is how derangements and surjection counts are computed.
The material
The principle
The two-set and three-set cases, the general statement, and why it is exact.
Theorem · Two and three sets
|A ∪ B| = |A| + |B| − |A ∩ B| and |A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|.
Theorem · Inclusion-exclusion
For finite sets A₁, …, A_n, |A₁ ∪ ⋯ ∪ A_n| = Σ|Aᵢ| − Σ_{i<j}|Aᵢ∩Aⱼ| + Σ_{i<j<k}|Aᵢ∩Aⱼ∩A_k| − ⋯ + (−1)^{n+1}|A₁∩⋯∩A_n| — an alternating sum over all nonempty subsets of the indices.
Take an element lying in exactly m of the sets, m ≥ 1. It is counted C(m,1) times in the first sum, C(m,2) times in the second, and so on, so its net contribution is C(m,1) − C(m,2) + C(m,3) − ⋯ = 1 − [C(m,0) − C(m,1) + C(m,2) − ⋯].
The bracket is the alternating row sum, which is 0 for m ≥ 1 (“Binomial Coefficients and Pascal's Triangle”). So the contribution is exactly 1.
An element in none of the sets contributes 0 to every term. Hence each element of the union is counted once and nothing else is counted.
□
That proof explains the signs rather than asserting them: they are exactly what is needed to make every element's contribution collapse to 1, and the collapse is the alternating-sum identity from Pascal's triangle.
The complement form
Theorem · Counting elements with none of the properties
If Aᵢ is the set of objects with property i, then the number with none of them is |U| − Σ|Aᵢ| + Σ|Aᵢ∩Aⱼ| − ⋯, the same alternating sum with the signs shifted.
Example · Divisibility
How many of 1, …, 1000 are divisible by none of 2, 3, 5? 1000 − (500 + 333 + 200) + (166 + 100 + 66) − 33 = 266. Each term is a floor division: ⌊1000/6⌋ = 166 counts the multiples of both 2 and 3.
That intersection term is ⌊N/6⌋ because 2 and 3 are coprime. In general the multiples of both a and b are the multiples of lcm(a, b), not of ab: of 1, …, 100, the numbers divisible by both 4 and 6 are the multiples of 12, ⌊100/12⌋ = 8 of them, and ⌊100/24⌋ = 4 undercounts. The lab computes every intersection through the lcm for exactly this reason.
Theorem · Euler's totient
The count of integers in 1, …, n coprime to n is φ(n) = n·Π(1 − 1/p) over the distinct primes p dividing n. That product is inclusion and exclusion over the prime divisors, multiplied out. Number Theory and Cryptography uses φ throughout.
Theorem · Counting surjections
The number of surjections from an m-set onto an n-set is Σ_{k=0}^{n} (−1)^k C(n,k)(n−k)^m — total functions minus those missing at least one target, corrected.
The pattern in all three: the direct count is hard and the count of "violates condition i" is easy, so count the violations and alternate. Recognising that shape is what this lesson is for.
Interactive
Inclusion and exclusion
Formula and brute force, side by side
Method
Applying inclusion and exclusion
Define the sets so the intersections are easy.
1
Define Aᵢ as "has property i"
Usually the bad property. Counting Aᵢ and its intersections must be easier than counting the objects you want.
2
Compute every intersection size
Pairs, triples, and so on. Symmetry often makes many of them equal, which is what keeps the sum manageable.
3
Alternate the signs
Add the singles, subtract the pairs, add the triples. Off by one in the sign pattern gives an answer that is wrong by twice the correction.
4
Sanity check the magnitude
The answer must lie between 0 and the total. A negative result means a sign error; a result above the total means a missed subtraction.
Inclusion and exclusion
Score 0 / 0Choose the answer you can justify.
Surjections from a 5-set onto a 3-set
How many functions from {1,…,5} onto {a,b,c} hit every target?
Total functions: 3⁵ = 243
Let Aₓ = functions that MISS target x.
|Aₓ| = 2⁵ = 32, and there are C(3,1) = 3 of them
|Aₓ ∩ A_y| = 1⁵ = 1, and there are C(3,2) = 3 of them
|Aₐ ∩ A_b ∩ A_c| = 0⁵ = 0
Functions missing at least one: 3·32 − 3·1 + 0 = 93
Surjections: 243 − 93 = 150
Formula check: Σ (−1)ᵏ C(3,k)(3−k)⁵
= 243 − 3·32 + 3·1 − 0 = 150 ✓
0⁵ = 0 is the right value here: no function can miss all three targets when the domain is nonempty. The convention 0⁰ = 1 would matter if the domain were empty, which is exactly the edge case such formulas are tested on.
Common mistakes
1
Getting the sign pattern wrongOdd-sized intersections are added, even-sized subtracted — in the union form. The complement form starts from the total and reverses. Write which form you are using.
2
Missing an intersection termWith n sets there are 2ⁿ − 1 terms. For four sets that is 15, and forgetting one silently changes the answer.
3
Assuming the intersections are all equalThey often are, by symmetry, and when they are not the count must be done term by term.
Check your understanding
✓
Finish when you can set up the sets so the intersections are easy.
Count the permutations of 1, …, 6 in which no element stays in its own position. Define Aᵢ as "element i is fixed", compute the intersections, and alternate. “Derangements” is that answer in general.
Note: The principle generalises far beyond counting: the same alternating structure appears in Möbius inversion, in the sieve methods of analytic number theory, and in the probabilistic version Discrete Probability uses for P(A ∪ B).