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

The Sieve Method in Practice

Using inclusion-exclusion as a sieve to filter and count elements systematically.

The Sieve Method in Practice

What you'll learn: How to systematically apply inclusion-exclusion as a filtering "sieve" to count elements that survive multiple constraints.

The Core Idea

The sieve method is inclusion-exclusion viewed as a filtering process. Instead of just computing a formula, you imagine "sieving out" unwanted elements step-by-step, carefully tracking overlaps. It's like filtering coffee: you remove grounds, but must account for what sticks in multiple filter layers.

In practice, you:

  1. Start with a universe of all candidates
  2. Define "bad" properties (things you want to exclude)
  3. Apply inclusion-exclusion to count items with none of the bad properties

This systematizes problems where direct counting is messy.

A Concrete Example

Problem: How many integers from 1 to 100 are not divisible by 2, 3, or 5?

  • Universe: 100 integers
  • Bad properties: A₂ = divisible by 2, A₃ = divisible by 3, A₅ = divisible by 5
  • We want |neither A₂ nor A₃ nor A₅|

Using inclusion-exclusion for "none of the properties":

100 − |A₂ ∪ A₃ ∪ A₅|
= 100 − (|A₂| + |A₃| + |A₅| − |A₂ ∩ A₃| − |A₂ ∩ A₅| − |A₃ ∩ A₅| + |A₂ ∩ A₃ ∩ A₅|)
= 100 − (50 + 33 + 20 − 16 − 10 − 6 + 3)
= 100 − 74 = 26

Notice how we "sieved": removed multiples of 2, 3, 5; added back double-counted overlaps; removed triple-counted ones.

Why "Sieve"?

The name evokes the ancient Sieve of Eratosthenes for primes—crossing out multiples systematically. Here, inclusion-exclusion formalizes that crossing-out with precise overlap correction.

Key Takeaway: The sieve method transforms inclusion-exclusion into a systematic filtering strategy, ideal for "count what remains after excluding overlapping bad properties."