Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 36 · Inclusion-Exclusion

Inclusion-Exclusion for Two and Three Sets

Count the union of overlapping sets without double counting. Learn the two-set and three-set inclusion-exclusion formulas, Venn diagrams and worked Python examples.

The sum rule works only when sets do not overlap. Real problems overlap constantly: students who study French or Spanish, numbers divisible by 2 or 3. The inclusion-exclusion principle corrects the sum so that every element is counted exactly once.

Two sets

If you add |A| + |B|, every element in both sets is counted twice. Subtract the intersection once:

|A ∪ B| = |A| + |B| - |A ∩ B|

Example: in a class of 40, 25 take French, 18 take Spanish, and 7 take both. Students taking at least one: 25 + 18 - 7 = 36, so 4 take neither.

Python Two-set 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.

Three sets

For three sets, adding the sizes counts elements in two sets twice and in all three thrice. Subtracting the pairwise intersections removes too much (an element in all three is now counted 3 - 3 = 0 times), so you must add the triple intersection back:

|A ∪ B ∪ C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|

Count how many times each region of a Venn diagram is counted. A region in exactly one set: counted once. In exactly two sets: 2 - 1 = 1. In all three: 3 - 3 + 1 = 1. Every element ends up counted exactly once.

flowchart TD
    S["Add the three sets"] --> P["Subtract the three pairwise overlaps"]
    P --> T["Add back the triple overlap"]
    T --> U["Union counted exactly once"]

Include, exclude, include again: the signs alternate.

Python Numbers up to 100 divisible by 2, 3 or 5

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.

Here the intersection of "divisible by 2" and "divisible by 3" is "divisible by 6", with floor(100/6) = 16 elements. In general the intersection of divisibility conditions is divisibility by the least common multiple.

Counting "none of the properties"

Often the question is the opposite: how many elements have none of the properties? Use the complement from Complement Counting and Casework: |U| - |A ∪ B ∪ C|. For the numbers 1 to 100 that are divisible by none of 2, 3, 5: 100 - 74 = 26. These are 1 and the numbers whose prime factors are all at least 7, up to 100.

Python Divisible by none of 2, 3, 5

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 survey example

A survey of 100 people: 60 like tea, 50 like coffee, 40 like juice; 30 like tea and coffee, 20 tea and juice, 25 coffee and juice; 10 like all three. How many like at least one? 60 + 50 + 40 - 30 - 20 - 25 + 10 = 85. So 15 like none. One check: no region may be negative. People liking only tea = 60 - 30 - 20 + 10 = 20, a valid number, and so on for the other regions.

Python Survey regions

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.

Check whether any region would come out negative. If it does, the survey numbers are inconsistent: a negative count is a quick data-quality test.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. If |A| = 12, |B| = 9 and |A ∩ B| = 4, what is |A ∪ B|?

    12 + 9 - 4 = 17.
  2. 2. How many integers from 1 to 60 are divisible by 3 or 5?

    Multiples of 3: 20, of 5: 12, of 15: 4, so 20 + 12 - 4 = 28.
  3. 3. In the three-set formula, why is |A∩B∩C| added back?

    Adding gives 3, subtracting the pairs gives 3 removals, leaving 0; adding the triple fixes it to 1.
  4. 4. Numbers up to 30 divisible by none of 2, 3 (count them)?

    30 - (15 + 10 - 5) = 10.

Summary

  • Two sets: |A ∪ B| = |A| + |B| - |A ∩ B|.
  • Three sets: add singles, subtract pairs, add the triple.
  • Intersections of divisibility conditions use the lcm.
  • "None of the properties" is the universe minus the union.

Next: The General Inclusion-Exclusion Formula