Skip to content

Lesson 9 · 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