Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 36 Ā· Inclusion-Exclusion

The General Inclusion-Exclusion Formula

State and prove the general inclusion-exclusion formula for n sets, implement it in Python, and use it to count bounded solutions and numbers coprime to a given value.

The two and three set formulas follow a pattern: add all single sets, subtract all pairs, add all triples, subtract all quadruples, and so on. This lesson states the general rule, proves it with a short counting argument, and shows the most common way to use it: counting objects that satisfy none of several "bad" properties.

The formula

For sets A1, A2, ..., An:

|A1 ∪ ... ∪ An| = Σ|Ai| - Σ|Ai ∩ Aj| + Σ|Ai ∩ Aj ∩ Ak| - ... + (-1)^(n+1) |A1 ∩ ... ∩ An|

Each sum runs over all subsets of that size. In compact form: sum over non-empty index sets S, with sign (-1)^(|S|+1), of |∩_{i in S} Ai|.

Proof idea. Take one element x that lies in exactly m >= 1 of the sets. On the right-hand side it is counted C(m, 1) - C(m, 2) + C(m, 3) - ... times. By the alternating sum identity from Pascal and the Binomial Theorem, Σ (-1)^k C(m, k) = 0 from k = 0, so C(m,1) - C(m,2) + ... = C(m, 0) = 1. Every element counts exactly once.

Python Implementing inclusion-exclusion

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 elements with none of the properties

Let U be the universe and Ai the set of elements with "bad" property i. The number with no bad property is

|U| - |A1 ∪ ... ∪ An| = Σ (-1)^|S| |∩_{i∈S} Ai| over all subsets S including the empty one (which contributes |U|).

This form is the workhorse. You compute |∩ Ai|, the number with at least the properties in S, which is usually easy, and let the signs sort out the rest.

Example: numbers coprime to n

How many integers from 1 to 60 are coprime to 60? The primes of 60 are 2, 3 and 5. Let Ap be the multiples of p. The numbers coprime to 60 are those in none of the sets. Multiples of p1 p2 number 60 / (p1 p2):

60 - (30 + 20 + 12) + (10 + 6 + 4) - 2 = 60 - 62 + 20 - 2 = 16.

This is Euler's totient φ(60) = 16, which we revisit in Surjections and Euler's Totient.

Python Coprime count by inclusion-exclusion

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.

Bounded stars and bars

Recall from Stars and Bars that bounded solutions need inclusion-exclusion. Count non-negative solutions of x1 + x2 + x3 = 12 with each xi <= 5.

Let Ai be the solutions with xi >= 6. Then |Ai| = solutions of the equation after subtracting 6: C(6 + 2, 2) = 28. Two violated variables use at least 6 + 6 = 12, leaving 0 to share: C(0 + 2, 2) = 1. Three violated is impossible. Total unrestricted C(14, 2) = 91. Answer: 91 - 3 x 28 + 3 x 1 = 10.

Python Bounded solutions

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.

The general idea is a "sieve": start with everything, throw out each bad property, put back what you threw out twice, throw out what you put back twice, and so on. That is why inclusion-exclusion is also called the sieve formula.

Cost and shortcuts

With n properties the formula has 2^n terms, so it is practical for roughly n <= 20. Often symmetry shrinks the work: when the size of an intersection depends only on how many sets are intersected, you group the C(n, j) equal terms (as in the bounded stars and bars example above and in Derangements).

flowchart LR
    U["Universe"] --> S["Subtract single bad sets"]
    S --> A["Add back pairs"]
    A --> T["Subtract triples"]
    T --> E["... until all subsets used"]

Signs alternate with the size of the chosen subset of properties.

Check your understanding

Quick check Ā· 4 questions

of 4 answered You scored / 4 Ā· perfect!

  1. 1. How many terms does the formula have for the union of 4 sets?

    One term for each non-empty subset of the 4 sets: 2^4 - 1 = 15.
  2. 2. How many integers from 1 to 30 are coprime to 30?

    30 - (15+10+6) + (5+3+2) - 1 = 8.
  3. 3. What is the sign of a term with an intersection of 3 sets in the union formula?

    Odd-sized intersections are added, even-sized are subtracted.
  4. 4. Why is every element counted exactly once?

    The alternating binomial sum equals 1 for every m >= 1.

Summary

  • |∪ Ai| is the alternating sum of intersection sizes over all subsets of the sets.
  • The proof uses the alternating binomial sum, so each element is counted once.
  • "None of the properties" is Ī£ (-1)^|S| |∩_S Ai|, including the empty set term |U|.
  • Uses: coprime counts, bounded distributions, and derangements next.

Next: Derangements