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

Counting with None of the Properties

Finding the complement: objects with none of the specified properties.

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:

  1. Start with the total number of objects
  2. 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.