inclusionexclusion

The inclusion-exclusion principle is a fundamental counting principle that determines the size of a union of overlapping sets by compensating for overcounting. It is widely used in combinatorics, probability, and various counting problems to avoid double counting elements that appear in multiple sets.

For two finite sets A and B, the size of their union is |A ∪ B| = |A| + |B| − |A ∩ B|. For a finite collection A1,...,An, the principle states |∪ Ai| = sum |Ai| − sum over i<j |Ai ∩ Aj| + sum over i<j<k |Ai ∩ Aj ∩ Ak| − ... + (−1)^{n+1} |A1 ∩ ... ∩ An|.

In probability, for events E1,...,En, P(∪ Ei) = sum P(Ei) − sum P(Ei ∩ Ej) + sum P(Ei ∩ Ej ∩ Ek) − ... + (−1)^{n+1} P(E1 ∩ ... ∩ En). The principle requires the events to be measurable, but it is widely used in discrete problems involving finite sets to compute likelihoods and expectations.

Example: If among 100 people, 60 like A, 50 like B, and 30 like both, then the number liking A or B is 60 + 50 − 30 = 80. For three sets A, B, and C with known sizes and intersections, |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

The principle helps avoid double counting and undercounting in counting problems, probability calculations, survey sampling, and set operations. It is related to Venn diagrams and can be generalized to finite collections; in some contexts, inclusion-exclusion can be extended with indicator variables and generating functions.