Technique Encyclopedia

Inclusion-Exclusion

What it is

When counting elements satisfying at least one of several conditions, simply adding the individual counts double-counts elements that satisfy more than one. Inclusion-exclusion corrects for this by subtracting the overlaps: for two sets, |A∪B| = |A| + |B| − |A∩B|; the pattern extends to three or more sets by alternately adding and subtracting deeper intersections.

Signals that suggest using it

Counting elements satisfying at least one of several stated conditions (often phrased with "or").
The conditions clearly overlap — some elements would be counted more than once by simple addition.
The individual sets and their intersections are each easy to count directly.

When it's effective

Works cleanly for two or three conditions whose pairwise (and triple) intersections are simple to compute — classic territory is counting multiples of several numbers up to some bound.

When it's not effective

With four or more overlapping sets, the number of intersection terms grows fast and the bookkeeping becomes error-prone — complementary counting or a cleverer bijection is often more reliable at that point.

Simple example

Problem

How many integers from 1 to 30 are multiples of 3 or multiples of 5?

Solution

Multiples of 3: 10. Multiples of 5: 6. Multiples of both (i.e. of 15): 2. 10+6-2=14.

AMC-style example

Problem

How many integers from 1 to 100 are divisible by 2 or by 3?

Solution

Divisible by 2: 50. Divisible by 3: 33. Divisible by 6 (both): 16. 50+33-16=67.

Complementary Counting Casework