Skip to content

The Inclusion–Exclusion Principle: Counting Overlaps Without Double-Counting

Inclusion–exclusion counts a union of overlapping sets: add the sets, subtract pairwise overlaps, add back triple overlaps. Formulas and four worked problems.

By Published 5 min read

Reign Creative LLC makes Discrete Math: Study & Quiz, which this article links to, so we have a commercial interest in it. How we write and check articles.

AI-assisted article. Drafted with AI tools from the sources cited below and checked by automated tests and an AI editorial review. No person has reviewed it yet. How we write and check articles.

Key takeaways

  • For two sets, |A ∪ B| = |A| + |B| − |A ∩ B|: adding the sets counts the overlap twice, so subtract it once.
  • For three sets, add the three sets, subtract the three pairwise overlaps and add back the triple overlap.
  • In general the signs alternate: add single sets, subtract pairs, add triples, and so on.
  • Many 'at least one' problems are easiest as total minus 'none', where 'none' is found by inclusion–exclusion.
  • The same method counts onto functions, derangements and integers coprime to n.

Counting the elements of one set is easy. Counting the elements of a union of sets that overlap is where people go wrong, because adding the sizes counts the shared elements more than once. The inclusion–exclusion principle is the bookkeeping that fixes this. Levin's Discrete Mathematics: An Open Introduction describes it as a process of adding in, then taking out, then adding back in, and so on, and abbreviates it PIE.

Two sets

If A and B overlap, |A| + |B| counts every element of A ∩ B twice. Subtract it once:

|A ∪ B| = |A| + |B| − |A ∩ B|.

Example. In a class of 30, 18 students play a sport and 12 play an instrument, and 7 do both. Then 18 + 12 − 7 = 23 do at least one, and 30 − 23 = 7 do neither.

That last step, total minus the union, is the most useful habit in this topic. Questions asking for "neither" or "none" are inclusion–exclusion problems in disguise.

Three sets

With three sets, subtracting the pairwise overlaps takes away too much, and the triple overlap has to be added back:

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

To see why, follow an element that is in all three sets. It is counted three times in the first sum, subtracted three times in the second, and so would be counted zero times without the final term. An element in exactly two sets is counted twice, subtracted once: once in total. An element in one set is counted once.

Example: languages. Of 40 students, 18 take French, 15 Spanish and 12 German. Six take French and Spanish, 5 French and German, 4 Spanish and German, and 2 take all three. Then

18 + 15 + 12 − 6 − 5 − 4 + 2 = 32

take at least one language, and 8 take none. Filling in a three-circle Venn diagram from the centre outwards is a good check: 2 in the middle, then 4, 3 and 2 in the pairwise-only regions, then the single-language regions.

The general formula

For n sets, add all the single sets, subtract all pairwise intersections, add all triple intersections, subtract all quadruple intersections, and so on, ending with the intersection of all n with sign (−1)ⁿ⁺¹. MathWorld gives this general form, and notes that the principle was used by Nicholas Bernoulli to count derangements.

Why does it work? An element in exactly r of the sets is counted

C(r, 1) − C(r, 2) + C(r, 3) − ⋯ ± C(r, r)

times. By the binomial theorem, (1 − 1)ʳ = 0 = 1 − C(r, 1) + C(r, 2) − ⋯, so the alternating sum above equals exactly 1. Every element of the union is counted once.

Worked problem 1: divisibility

How many integers from 1 to 100 are divisible by 2, 3 or 5?

Let A₂, A₃, A₅ be the multiples of 2, 3 and 5 up to 100. A number is in A₂ ∩ A₃ exactly when it is a multiple of 6, and so on.

Set Count
Multiples of 2 50
Multiples of 3 33
Multiples of 5 20
Multiples of 6 16
Multiples of 10 10
Multiples of 15 6
Multiples of 30 3

So 50 + 33 + 20 − 16 − 10 − 6 + 3 = 74 numbers are divisible by at least one of them, and 100 − 74 = 26 by none.

The same calculation for divisors of a number gives Euler's totient. The integers from 1 to 30 sharing no factor with 30 = 2 · 3 · 5 number 30 − (15 + 10 + 6) + (5 + 3 + 2) − 1 = 8.

Worked problem 2: bit strings

How many 8-bit strings start with 1 or end with 00? Starting with 1: 2⁷ = 128. Ending with 00: 2⁶ = 64. Both: 2⁵ = 32. Answer: 128 + 64 − 32 = 160.

Worked problem 3: onto functions

How many functions from a 5-element set onto a 3-element set {a, b, c}?

There are 3⁵ = 243 functions in all. Count the ones that miss at least one output. Functions missing a: 2⁵ = 32, and likewise for b and c. Missing both a and b: 1⁵ = 1, and likewise for the other two pairs. Missing all three: 0. So

243 − (3 · 32) + (3 · 1) − 0 = 150

functions are onto. This "total minus the bad ones" pattern is how surjections are usually counted.

Worked problem 4: upper limits in distributions

Levin's book applies PIE to distribution problems with a cap. Distributing 10 identical sweets to 3 children with no child getting more than 4: without the cap, stars and bars gives C(12, 2) = 66 ways. If one particular child gets at least 5, give that child 5 first and distribute the other 5 freely: C(7, 2) = 21 ways, times 3 children. Two children can both get 5 or more only by getting exactly 5 each, leaving the third with none: 1 way for each of the 3 pairs. Three children with 5 or more would need 15. So 66 − 63 + 3 = 6 ways. (Check: the distributions are the arrangements of 4, 4, 2 and 4, 3, 3, three of each.)

Recognising an inclusion–exclusion problem

  • The question says "at least one", "none", "neither" or "not divisible by any".
  • The conditions overlap: a number can be a multiple of both 2 and 3.
  • The intersections are easier to count than the union.

The most famous application is counting derangements, permutations in which nothing stays in its original place, which follows from the formula with n sets.

Discrete Math: Study & Quiz has a combinatorics unit, broken into topics and lessons with knowledge checks, and topic and timed quizzes for practice. The app is listed with our education and brain-training apps, and the discrete math hub has the rest of the counting series.

Good to know

Frequently asked questions

What is the inclusion–exclusion principle?
A rule for counting the elements in a union of overlapping sets. Add the sizes of the sets, subtract the sizes of all pairwise intersections, add the sizes of all triple intersections, and continue alternating. Each element ends up counted exactly once.
What is the inclusion–exclusion formula for three sets?
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|. The triple intersection is added back because it was added three times and then subtracted three times.
How many numbers from 1 to 100 are divisible by 2, 3 or 5?
74. There are 50 multiples of 2, 33 of 3 and 20 of 5; subtract 16 multiples of 6, 10 of 10 and 6 of 15; add back 3 multiples of 30. 50 + 33 + 20 − 16 − 10 − 6 + 3 = 74, so 26 numbers are divisible by none of them.
Why does inclusion–exclusion count each element exactly once?
An element in exactly r of the sets is counted C(r, 1) − C(r, 2) + C(r, 3) − ⋯ times. By the binomial theorem that alternating sum equals 1 for every r ≥ 1, so every element of the union is counted once.

Sources

  1. Additive and Multiplicative Principles: Principle of Inclusion/Exclusion (Discrete Mathematics: An Open Introduction, 3rd edition, Oscar Levin) (opens in a new tab)Open Math Books — accessed
  2. Advanced Counting Using PIE (Discrete Mathematics: An Open Introduction, 3rd edition, Oscar Levin) (opens in a new tab)Open Math Books — accessed
  3. Inclusion-Exclusion Principle (opens in a new tab)Wolfram MathWorld — accessed

About the author

— The independent app studio that builds the apps covered on this site and publishes every article here. On Google Play it publishes as Reign Collective Apps.

We use AI tools to help research, draft and edit our articles. Each article lists the sources its factual claims rely on, and details about our apps come from their live Google Play listings. No article on this site has been reviewed by an independent expert unless the reviewer is named on it.

No person at Reign Creative LLC has read this article in full. It was published after automated checks and an AI editorial review, which are described in our editorial policy and are not the same as a person reading every sentence.

Spotted an error? Tell us — how corrections are handled is set out in our editorial policy.

Keep reading