Inclusion-Exclusion Principle — Mathematics Knowledge System

Overview

The inclusion-exclusion principle is a counting technique for finding the size of a union of overlapping sets without double-counting elements that belong to more than one. For two sets it says |A∪B| = |A|+|B|-|A∩B|, subtracting off the overlap counted twice. For more sets, the pattern alternates: add the singles, subtract the pairwise intersections, add back the triple intersections, and so on. It is one of the most widely used tools in combinatorics, underlying derangement counts, sieve methods in number theory, and probability calculations involving overlapping events.

Intuition

Imagine adding up |A| and |B| to estimate |A∪B|: anything in both sets got counted twice, so you subtract |A∩B| once to fix it. With three sets the fix has to go further — elements in exactly two sets were over-corrected, and elements in all three sets end up net undercounted after the pairwise subtractions, so you add the triple intersection back. The pattern of alternating + and − signs exactly compensates for how many times each element was counted at each stage, and it generalizes to any number of sets.

Formal Definition

Definition

For finite sets A₁,…,Aₙ, the size of their union is given by the alternating sum over all nonempty subsets of indices:

|A \cup B| = |A| + |B| - |A \cap B|

Two-set case

|A \cup B \cup C| = |A|+|B|+|C| - |A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C|

Three-set case

\left| \bigcup_{i=1}^{n} A_i \right| = \sum_{i} |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i\cap A_j\cap A_k| - \cdots + (-1)^{n-1}|A_1\cap\cdots\cap A_n|

General n-set formula

Worked Examples

Let A = multiples of 2, B = multiples of 3 within 1..100.
$|A| = \lfloor 100/2 \rfloor = 50, \quad |B| = \lfloor 100/3 \rfloor = 33$
The overlap is multiples of lcm(2,3)=6.
$|A \cap B| = \lfloor 100/6 \rfloor = 16$
Apply inclusion-exclusion.
$|A \cup B| = 50 + 33 - 16 = 67$

Answer: 67 integers.

Practice Problems

Difficulty 3/10

How many integers from 1 to 50 are divisible by 4 or 6?

Difficulty 5/10

Of 100 survey respondents, 60 like tea, 50 like coffee, and 20 like both. How many like tea or coffee?

Difficulty 6/10

Among 200 people, 100 read newspaper X, 80 read Y, 60 read Z, 40 read both X and Y, 30 read both X and Z, 20 read both Y and Z, and 10 read all three. How many read at least one newspaper?

Quiz

Summary

Inclusion-exclusion corrects for double-counting when summing the sizes of overlapping sets.
The two-set formula |A∪B|=|A|+|B|-|A∩B| generalizes to an alternating sum over all subset intersections for n sets.
It is the key tool behind counting derangements, solving 'divisible by neither/either' problems, and sieve-style arguments.

References

WebsiteWikipedia — Inclusion–exclusion principle