Principle of Inclusion/Exclusion

Overview

The principle of inclusion/exclusion refers to the oscillating adding and subtracting used to find the cardinality of potentially overlapping sets. Consider sets $A$, $B$, and $C$. Then

$|A\cup B|=|A|+|B|-|AB|$

and

$|A\cup B\cup C|=|A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC|$

Notice the number of terms containing one set, two sets, three sets, etc. match the binomial coefficients.

Bibliography

• Oscar Levin, Discrete Mathematics: An Open Introduction, 3rd ed., n.d., https://discrete.openmathbooks.org/pdfs/dmoi3-tablet.pdf.