Lemma › Guides › Inclusion-exclusion principle in competition math
Guide

Inclusion-exclusion principle in competition math

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 A1,A2,…,AnA_1, A_2, \dots, A_n,

∣A1∪⋯∪An∣=∑∣Ai∣−∑∣Ai∩Aj∣+∑∣Ai∩Aj∩Ak∣−⋯|A_1 \cup \dots \cup A_n| = \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - \cdots

Singles are added, pairs are subtracted, triples are added back, and so on, alternating. For two sets it is ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A \cup B| = |A| + |B| - |A \cap B|. For three, it adds the last term +∣A∩B∩C∣+ |A \cap B \cap C|.

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 11 to 100100 are divisible by 22, 33 or 55?

Let AA, BB, CC be the multiples of 22, 33 and 55. The singles are 5050, 3333 and 2020. Pairs are multiples of 66, 1010 and 1515, which number 1616, 1010 and 66. The triple is the multiples of 3030, which number 33. So

50+33+20−16−10−6+3=74.50 + 33 + 20 - 16 - 10 - 6 + 3 = 74.

The numbers from 11 to 100100 with no factor 22, 33 or 55 are the other 2626.

Why the signs work

Take any element that lies in exactly mm of the sets, with m≥1m \ge 1. In the first sum it is counted (m1)\binom{m}{1} times. In the pairs sum it is counted (m2)\binom{m}{2} times, and so on. Its total contribution is

(m1)−(m2)+(m3)−⋯=1.\binom{m}{1} - \binom{m}{2} + \binom{m}{3} - \cdots = 1.

This holds because (1−1)m=0(1 - 1)^m = 0. Expand it and the alternating sum of all the binomial coefficients is zero, starting with (m0)=1\binom{m}{0} = 1. Move that 11 to the other side and the sum above is 11. 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 11 to 10001000 that are divisible by none of 44, 66 and 1010.

The singles are ⌊1000/4⌋=250\lfloor 1000/4 \rfloor = 250, then 166166 and 100100. The pairs: lcm⁡(4,6)=12\operatorname{lcm}(4, 6) = 12 gives 8383, lcm⁡(4,10)=20\operatorname{lcm}(4, 10) = 20 gives 5050, lcm⁡(6,10)=30\operatorname{lcm}(6, 10) = 30 gives 3333. The triple: lcm⁡(4,6,10)=60\operatorname{lcm}(4, 6, 10) = 60 gives 1616. So the union has

250+166+100−83−50−33+16=366250 + 166 + 100 - 83 - 50 - 33 + 16 = 366

elements, and the count with none of the three is 1000−366=6341000 - 366 = 634. Had you used the product 4⋅6=244 \cdot 6 = 24 for the first pair you would have got 4141 instead of 8383, and the error propagates.

Four kinds of problem it solves

1. Divisibility counts. The example above. Whenever a problem asks for numbers up to NN avoiding several divisors.

2. Derangements. A derangement of nn objects is an ordering with no object in its own place. Let AiA_i be the orderings that fix object ii. Then ∣Ai1∩⋯∩Aik∣=(n−k)!|A_{i_1} \cap \dots \cap A_{i_k}| = (n - k)!, and there are (nk)\binom{n}{k} ways to choose which kk objects are fixed. So the number with none fixed is

Dn=∑k=0n(−1)k(nk)(n−k)!=n!∑k=0n(−1)kk!.D_n = \sum_{k=0}^{n} (-1)^k \binom{n}{k}(n-k)! = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}.

With n=4n = 4: 24−24+12−4+1=924 - 24 + 12 - 4 + 1 = 9. With n=5n = 5: 120−120+60−20+5−1=44120 - 120 + 60 - 20 + 5 - 1 = 44.

3. Surjections. How many functions from a 44-element set onto a 33-element set? Let AiA_i be the functions that miss the iith value. Each AiA_i has 242^4 functions, each pair has 141^4, and the triple would need a function missing all three values, of which there are 04=00^4 = 0. So

34−3⋅24+3⋅14=81−48+3=36.3^4 - 3 \cdot 2^4 + 3 \cdot 1^4 = 81 - 48 + 3 = 36.

4. Euler's totient. The numbers up to nn coprime to nn are those divisible by none of its prime factors. For n=30n = 30, remove multiples of 22, 33 and 55 and you are left with 30⋅12⋅23⋅45=830 \cdot \frac12 \cdot \frac23 \cdot \frac45 = 8. The general formula φ(n)=n∏p∣n(1−1p)\varphi(n) = n\prod_{p \mid n}\left(1 - \frac1p\right) 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 kk bad events is easy to count, and depends only on kk, 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 AiA_i before you write any numbers. The problem archive has plenty.

Related guides

Techniques in this guide

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