Counting with At Least One Property
You'll learn how to use the inclusion-exclusion principle to count objects that satisfy at least one condition from a set of possible conditions.
The Core Idea
When you need to count how many items have at least one of several properties, directly enumerating them is often tedious or error-prone. The inclusion-exclusion principle provides an elegant shortcut: count everything satisfying the first property, add everything satisfying the second property, and so on—but carefully subtract the overlaps to avoid double-counting.
For properties P₁, P₂, ..., Pₙ, the count of objects with at least one property is:
|P₁ ∪ P₂ ∪ ... ∪ Pₙ|
Using the general inclusion-exclusion principle you've learned, this equals the alternating sum of individual property counts, minus pairwise intersections, plus triple intersections, and so on.
Why "At Least One" Matters
This phrasing signals that you're looking at a union of sets. An object qualifies if it has property P₁ or P₂ or P₃ (or any combination). This is exactly what inclusion-exclusion was designed to handle.
Example Scenario
Suppose you want to count integers from 1 to 100 divisible by 2, 3, or 5. That's "at least one" of three properties:
- P₁: divisible by 2 (50 numbers)
- P₂: divisible by 3 (33 numbers)
- P₃: divisible by 5 (20 numbers)
Apply inclusion-exclusion: Add individual counts, subtract pairwise overlaps (divisible by 6, 10, 15), then add back the triple overlap (divisible by 30).
Key Takeaway: When counting objects satisfying at least one of several conditions, use inclusion-exclusion to systematically account for all overlaps and arrive at the exact count without manual enumeration.