Counting with None of the Properties
What you'll learn: How to count objects that satisfy none of a collection of specified properties using the complement approach with inclusion-exclusion.
The Core Idea
When we want to count objects with none of several properties, we use the complement of the union. Instead of directly counting objects avoiding all properties (which can be messy), we:
- Start with the total number of objects
- Subtract all objects having at least one property
This transforms a difficult "none" problem into a manageable "at least one" problem that we already know how to solve with inclusion-exclusion.
The Formula
If we have a universal set U and properties P₁, P₂, ..., Pₙ, then:
Objects with none of the properties = |U| − |P₁ ∪ P₂ ∪ ... ∪ Pₙ|
We compute the union using the inclusion-exclusion principle from the previous lesson.
A Simple Example
Problem: How many integers from 1 to 100 are divisible by neither 3 nor 5?
- Total integers: |U| = 100
- Let P₁ = divisible by 3, P₂ = divisible by 5
- |P₁| = 33, |P₂| = 20, |P₁ ∩ P₂| = 6 (divisible by 15)
- |P₁ ∪ P₂| = 33 + 20 − 6 = 47
- Answer: 100 − 47 = 53 integers
Why This Works
Think of a guest list where some people are vegetarian, some are allergic to nuts, etc. Finding people with no dietary restrictions is easier by taking everyone and removing those with any restriction—rather than checking each person individually.
Key Takeaway: To count objects with none of several properties, subtract the count of objects with at least one property from the total—turning a "none" problem into a complement you solve with inclusion-exclusion.