Inclusion-exclusion counts the size of a union without counting anything twice. It is easy to state and easy to botch, because the signs alternate and the pieces get complicated quickly. The formula is short. The skill is recognising a problem phrased as "none of these" or "at least one of these" and knowing that the complement is where you should work.
The statement
For sets ,
Singles are added, pairs are subtracted, triples are added back, and so on, alternating. For two sets it is . For three, it adds the last term .
Most of the time you want the opposite count, the elements in none of the sets. That is the total minus the union.
An example you can do by hand
How many integers from to are divisible by , or ?
Let , , be the multiples of , and . The singles are , and . Pairs are multiples of , and , which number , and . The triple is the multiples of , which number . So
The numbers from to with no factor , or are the other .
Why the signs work
Take any element that lies in exactly of the sets, with . In the first sum it is counted times. In the pairs sum it is counted times, and so on. Its total contribution is
This holds because . Expand it and the alternating sum of all the binomial coefficients is zero, starting with . Move that to the other side and the sum above is . Every element in the union is counted exactly once, and elements in no set are counted zero times.
That argument is the whole proof, and it is short enough to write out in an exam when someone asks you to justify the method.
The part where people lose marks: intersections are lcms
When the sets are multiples of numbers, the intersection is the multiples of the lcm, not the product. Count the integers from to that are divisible by none of , and .
The singles are , then and . The pairs: gives , gives , gives . The triple: gives . So the union has
elements, and the count with none of the three is . Had you used the product for the first pair you would have got instead of , and the error propagates.
Four kinds of problem it solves
1. Divisibility counts. The example above. Whenever a problem asks for numbers up to avoiding several divisors.
2. Derangements. A derangement of objects is an ordering with no object in its own place. Let be the orderings that fix object . Then , and there are ways to choose which objects are fixed. So the number with none fixed is
With : . With : .
3. Surjections. How many functions from a -element set onto a -element set? Let be the functions that miss the th value. Each has functions, each pair has , and the triple would need a function missing all three values, of which there are . So
4. Euler's totient. The numbers up to coprime to are those divisible by none of its prime factors. For , remove multiples of , and and you are left with . The general formula is inclusion-exclusion over the primes, with the sums collapsed into a product.
How to spot it
The phrases to look for are "none of", "at least one of", "not divisible by any", "no person gets their own", "onto" and "every colour is used". All of them describe a union or its complement over a list of bad events.
The test for whether it is worth the effort is how the intersections look. If the intersection of any bad events is easy to count, and depends only on , inclusion-exclusion collapses to a clean sum, as in derangements and surjections. If the intersections are messy and different from each other, use a direct construction instead.
Where it sits
This is the counting habit from constructive counting: decide what the good objects are, and count the bad ones when that is easier. For practice, take six problems that say "none of" and for each one write the bad events before you write any numbers. The problem archive has plenty.
Related guides
- Chicken McNugget theorem: the proof and the formulaFor coprime a and b the largest total you cannot make is ab - a - b. The proof, the count of unmakeable totals, and what breaks with three sizes.
- Stars and bars: counting solutions, with the trapsStars and bars counts the ways to split n identical objects into k boxes. Both formulas, the shift for minimums, the cap trap, and worked examples.
- Constructive vs complementary counting: which one to reach forTwo ways to count the same set, and one question that tells you which is cheaper. The signals, the worked pair, and the trap where the obvious tell lies to you.
- Generating functions: turning a counting problem into a productGenerating functions explained as a method: one factor per constraint, multiply, read the coefficient. The dictionary, and how to extract by hand.
- How a double counting proof is actually builtDouble counting proofs are always the same three steps, and only one of them is hard. The skeleton, five worked examples, and where they go wrong.
Techniques in this guide
- Constructive Counting & OvercountingBuild the object step by step, then divide by what you repeated.
Train it on Lemma
Every technique here is taught explicitly, in order. 128 lessons, 1237 curated problems and unlimited generated practice at six difficulties. Free to start, no card, and the paid plan opens with 3 free days.
Find your level