inclusion–exclusion principle

The inclusion–exclusion principle describes the cardinality of the union of 2 sets as

For 3 sets:

In general,

Theorem

suppose are finite sets,

Proof

Suppose but for some . The element is counted this many times by the RHS:

because the alternative sum of binomial coefficient for .