Inclusion–exclusion principle

A counting principle that computes the size of a union by adding set sizes, subtracting pairwise overlaps, and alternating through higher-order intersections.

Principle of inclusion and exclusion for two sets: The identity that the size of two sets’ union equals their sizes’ sum minus the size of their intersection. This simplest case shows how subtracting the overlap repairs double-counting.
Derangements: Permutations with no fixed points. Inclusion–exclusion counts permutations that avoid every fixed-point condition.
Set union: The set of elements that belong to at least one of a collection of sets. The principle’s target is the size of this combined set.
Abraham de Moivre: A French-born mathematician known for work in probability, trigonometry, and analytic approximations. His work helped develop early systematic treatments of the counting method.
Indicator function: A function that takes value one when a condition holds and zero otherwise. Summing indicators turns union counting into a pointwise alternating-sum identity.
Coupon collector's problem: A probability problem asking how many random draws are needed to collect every coupon type. Inclusion–exclusion computes the chance that at least one coupon type remains unseen.
Set intersection: The set of elements shared by every set in a collection. Intersections supply the overlap terms that correct the union count.
Pierre-Simon Laplace: A French mathematician and astronomer who made foundational contributions to probability and celestial mechanics. Laplace used the principle in probability and helped establish its standard form.
Binomial theorem: The formula expanding an integer power of a sum into binomially weighted terms. Binomial coefficients encode how often each element appears in the alternating corrections.
Sieve theory: A family of methods for estimating or counting integers that avoid specified divisibility conditions. Sieve methods use inclusion–exclusion to remove integers divisible by selected primes.

Linked from 19 pages