Inclusion-Exclusion

← Back to Combinatorics

A counting principle for the size of the union of sets: |A union B| = |A| + |B| - |A intersect B|. Generalizes to n sets by alternately adding and subtracting intersection sizes. Used in derangements, Euler’s totient function, and probability calculations.

mathematics-for-cs discrete-mathematics combinatorics inclusion-exclusion