The inclusion-exclusion principle generalizes the sum rule to compute the cardinality of a union of possibly overlapping sets: for two sets it is |M∪E| = |M| + |E| − |M∩E|, and in general it alternates adding the cardinalities of all single sets, subtracting all pairwise intersections, adding all triple intersections, and so on, with sign (−1)^(k+1) for k-fold intersections, terminating at the full n-set intersection. This principle belongs to combinatorics/discrete mathematics, sits alongside the sum rule, product rule, division rule (for k-to-one mappings), the bijection rule (for counting via bijective correspondence), the bookkeeper/multinomial rule, and the binomial theorem, and underlies combinatorial-proof technique — proving an identity by counting the same set two different ways.
The inclusion-exclusion principle generalizes the sum rule to compute the cardinality of a union of possibly overlapping sets: for two sets it is |M∪E| = |M| + |E| − |M∩E|, and in general it alternat…