Inclusion-Exclusion Principle
For finite sets, : alternately add and subtract intersections so every element is counted once.
Small cases
One should have seen the following formulae before:
Proof via indicator functions
An alternative proof uses indicator functions, together with the fact that if then
Proof
Let , say for of the sets . We want to be counted exactly once in the RHS.
Indeed, for with , the intersections containing correspond to choosing of the sets that contain , giving of them when and otherwise. Thus the number of times is counted on the RHS is
Related
Stated in
- Theorem 3.16 (Inclusion-Exclusion Principle)§3.3.2 Inclusion-Exclusion Principle