Course contentsShow
← Computer Science
Lesson 106 of 2,8722. Discrete Mathematics for CSFree lesson

Inclusion-Exclusion Principle

Count elements in unions of sets by alternately adding and subtracting intersections to avoid double-counting.

Inclusion-Exclusion Principle

What You'll Learn

You'll learn how to count elements in the union of multiple sets without counting the same element more than once.

The Core Problem

Imagine you're counting students who take either Math or CS. If you simply add "students in Math" plus "students in CS," you've double-counted everyone taking both classes!

The Inclusion-Exclusion Principle fixes this by systematically correcting for overlaps.

The Formula

For two sets A and B:

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

We include the individual sets, then exclude the intersection to remove the double-count.

For three sets A, B, and C:

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

Notice the pattern: add singles, subtract pairs, add triples.

Why It Works

When you add |A| + |B| + |C|, elements in two sets get counted twice, and elements in all three get counted three times. Subtracting the pairwise intersections fixes the doubles, but now elements in all three have been removed too many times (once for each pair), so we add back |A ∩ B ∩ C|.

Example

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

  • Divisible by 2: 50 numbers
  • Divisible by 3: 33 numbers
  • Divisible by both (6): 16 numbers

Answer: 50 + 33 - 16 = 67 numbers

Key Takeaway: The Inclusion-Exclusion Principle counts union sizes by alternating addition and subtraction of intersections—ensuring every element is counted exactly once.