Skip to content
Tutorials Center
My learning

Topics

Lesson 9 of 38 Ā· Sets and Operations

Inclusion-Exclusion

Learn the inclusion-exclusion principle for two, three and n sets, apply it to counting problems and derangements, and verify it with code.

How many integers from 1 to 100 are divisible by 2 or by 3? You cannot just add "multiples of 2" and "multiples of 3", because multiples of 6 are counted twice. The inclusion-exclusion principle is the systematic way to fix such double counting. It is one of the most useful tools for counting, and it is a direct consequence of how unions work.

Two sets

For finite sets A and B:

Text
|A ∪ B| = |A| + |B| āˆ’ |A ∩ B|

Add the sizes (this counts the overlap twice), then subtract the overlap once.

Example. Count the integers from 1 to 100 divisible by 2 or by 3. Let A be the multiples of 2 and B the multiples of 3.

  • |A| = 50 (since 100 / 2 = 50).
  • |B| = 33 (since the largest multiple of 3 not above 100 is 99 = 3 Ā· 33).
  • A ∩ B is the multiples of 6: |A ∩ B| = 16 (since 6 Ā· 16 = 96 ≤ 100 < 102).

So |A ∪ B| = 50 + 33 āˆ’ 16 = 67.

Three sets

For three sets the correction has an extra twist:

Text
|A ∪ B ∪ C| = |A| + |B| + |C|
              āˆ’ |A ∩ B| āˆ’ |A ∩ C| āˆ’ |B ∩ C|
              + |A ∩ B ∩ C|

Why does the last term come back with a plus sign? An element in all three sets is counted 3 times by the first line, removed 3 times by the pairwise terms, so it ends up counted 0 times. The triple term adds it back to make exactly 1. Elements in exactly two sets are counted 2 āˆ’ 1 = 1 time. Elements in exactly one set are counted once. Every region is counted exactly once, as it should be.

The general formula

For n finite sets A₁, ..., Aā‚™ the signs alternate with the number of sets intersected:

Text
|A₁ ∪ ... ∪ Aā‚™| = Ī£|Aįµ¢| āˆ’ Ī£|Aįµ¢ ∩ Aā±¼| + Ī£|Aįµ¢ ∩ Aā±¼ ∩ Aā‚–| āˆ’ ... + (āˆ’1)ⁿ⁺¹ |A₁ ∩ ... ∩ Aā‚™|

where each sum runs over all choices of that many sets. There are C(n, k) terms for the k-set intersections.

Why it works. Take an element that lies in exactly m ≄ 1 of the sets. In the k-th sum it is counted C(m, k) times, with sign (āˆ’1)įµāŗĀ¹. The total count is C(m,1) āˆ’ C(m,2) + C(m,3) āˆ’ ... ± C(m,m). Since the alternating sum C(m,0) āˆ’ C(m,1) + ... ± C(m,m) equals 0 for m ≄ 1 (the binomial theorem for (1 āˆ’ 1)ᵐ), this total equals C(m,0) = 1. Every element in the union is counted exactly once.

Python Inclusion-exclusion by code

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Counting what is not in any set

Often it is easier to count the complement. If U is the universe of size N, then

Text
|(A₁ ∪ ... ∪ Aā‚™)ᶜ| = N āˆ’ |A₁ ∪ ... ∪ Aā‚™|

Example. How many integers from 1 to 100 are divisible by none of 2, 3, 5? The union of the three multiples sets has size

50 + 33 + 20 āˆ’ 16 āˆ’ 10 āˆ’ 6 + 3 = 74,

where |A ∩ B| = 16 (multiples of 6), |A ∩ C| = 10 (multiples of 10), |B ∩ C| = 6 (multiples of 15) and |A ∩ B ∩ C| = 3 (multiples of 30: 30, 60, 90). So 100 āˆ’ 74 = 26 numbers are not divisible by 2, 3 or 5. This is how Euler's totient function counts numbers coprime to n.

A classic: derangements

A derangement is a rearrangement of n objects where no object stays in its original place. Let Aįµ¢ be the set of arrangements where object i stays put. Fixing k specific objects leaves (n āˆ’ k)! arrangements, and there are C(n, k) ways to choose those objects. Inclusion-exclusion gives

Text
D(n) = n! āˆ’ C(n,1)(nāˆ’1)! + C(n,2)(nāˆ’2)! āˆ’ ... + (āˆ’1)ⁿ C(n,n) 0!

For example D(3) = 6 āˆ’ 3Ā·2 + 3Ā·1 āˆ’ 1 = 2 (the two cyclic shifts of three objects). The program below counts derangements both ways and compares.

Python Derangements: formula versus brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A strategy for counting problems

  1. Define the "bad" or "wanted" sets A₁, ..., Aā‚™ clearly.
  2. Work out the size of every intersection (often they depend only on how many sets you intersect).
  3. Apply the alternating sum.
  4. Sanity check with a small case or by computer.

Inclusion-exclusion is most powerful when all the k-fold intersections of a given k have the same size, so the sum collapses into a single formula using C(n, k).

Check your understanding

Quick check Ā· 4 questions

of 4 answered You scored / 4 Ā· perfect!

  1. 1. If |A| = 20, |B| = 15 and |A ∩ B| = 6, what is |A ∪ B|?

    20 + 15 - 6 = 29.
  2. 2. How many integers from 1 to 60 are divisible by 4 or by 6?

    Multiples of 4: 15. Multiples of 6: 10. Multiples of both are multiples of 12: 5. So 15 + 10 - 5 = 20.
  3. 3. In the three-set formula, why is |A ∩ B ∩ C| added back?

    Such elements are counted 3 times, then subtracted 3 times, so they need to be added once to count exactly once.
  4. 4. What is D(3), the number of derangements of 3 objects?

    6 - 3Ā·2 + 3Ā·1 - 1 = 2. The two derangements are the cyclic shifts.

Summary

  • |A ∪ B| = |A| + |B| āˆ’ |A ∩ B|; for three sets add back the triple intersection.
  • In general, add single sets, subtract pairs, add triples, and so on with alternating signs.
  • Each element of the union is counted exactly once because an alternating sum of binomial coefficients is 0.
  • Use it to count elements in none of the sets and to count derangements.

Next: Ordered Pairs and Cartesian Products