Course contentsShow
← Mathematics
Lesson 2618 of 3,12152. CombinatoricsFree lesson

Inclusion-Exclusion for Three Sets

Extending the principle to three sets with alternating additions and subtractions.

Inclusion-Exclusion for Three Sets

What you'll learn: You'll extend the two-set inclusion-exclusion principle to count elements in the union of three sets by alternating additions and subtractions.

The Core Idea

When counting elements in the union of three sets A, B, and C, you can't just add up their sizes—you'll overcount! Elements in overlaps get counted multiple times. The Inclusion-Exclusion Principle for Three Sets corrects this by:

  1. Adding the sizes of individual sets (|A| + |B| + |C|)
  2. Subtracting the pairwise intersections (−|A∩B| − |A∩C| − |B∩C|), since we counted these twice
  3. Adding back the three-way intersection (+|A∩B∩C|), since we subtracted it too many times

The formula:

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

Why the Alternating Pattern?

Think of it like adjusting a balance scale:

  • Start by adding all sets (overcounts overlaps)
  • Subtract pairs (corrects double-counts, but now elements in all three sets have been removed entirely!)
  • Add back the triple intersection (restores those wrongly-removed elements)

Each element in A∩B∩C is counted: +1 (from A) +1 (from B) +1 (from C) −1 (from A∩B) −1 (from A∩C) −1 (from B∩C) +1 (from A∩B∩C) = exactly 1 time.

Example

If |A|=50, |B|=40, |C|=30, |A∩B|=10, |A∩C|=8, |B∩C|=7, |A∩B∩C|=3:

|A ∪ B ∪ C| = 50 + 40 + 30 − 10 − 8 − 7 + 3 = 98

Key Takeaway: The inclusion-exclusion principle for three sets uses alternating signs—add individual sets, subtract pairs, add triples—to count union elements exactly once.