Learning path

Full curriculum

Full curriculum

Arrows go from each prerequisite to the units that depend on it. Hover or focus a unit to highlight its path.

Unit content

Inclusion-exclusion principle

When several sets overlap, simply adding their sizes counts elements in the overlap more than once. The inclusion-exclusion principle corrects that overcounting.

For two finite sets,

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

The intersection is subtracted because its elements were counted once in $A$ and once in $B$.

For three sets,

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

The signs alternate because each correction can itself remove or add some elements too many times.

Inclusion-exclusion turns overlapping conditions into exact counts and appears in probability, combinatorics and counting constrained objects.