The inclusion–exclusion principle is a fundamental identity in combinatorics that determines the size of a union of finite sets from the sizes of their intersections. Adding the sizes of the individual sets counts shared elements more than once; subtracting pairwise intersections corrects some of this overcounting, but requires further corrections for higher-order intersections. The resulting alternating sum counts each element of the union exactly once. The same identity applies to probabilities, finite measures, and weighted counting.
Basic formulas
For two finite sets and ,
where denotes the cardinality of . An element belonging to both sets appears twice in , so subtracting leaves one copy.
For three finite sets,
An element in all three sets is initially counted three times and then subtracted three times. The final term restores its contribution to one.
For example, suppose three clubs have 30, 25, and 20 members. Their pairwise intersections have 10, 8, and 5 members, and 3 people belong to all three clubs. The number belonging to at least one club is
Here each pairwise intersection includes the people who also belong to the third club; it does not mean membership in exactly those two clubs.
General statement
Let be finite sets, with , and write . Then
Equivalently, grouping terms by the number of sets intersected,
Thus single-set counts are added, two-set intersections are subtracted, three-set intersections are added, and the signs continue alternating.
A closely related formula counts objects that avoid every listed property. If all are subsets of a finite universe , then
with the convention
The empty-index term is therefore . This formulation is often used by treating as the set of objects violating the -th requirement.
Why the formula works
Counting the contribution of one element
Suppose an element belongs to exactly of the sets. It belongs to precisely of their -fold intersections, where is a binomial coefficient. Its total contribution to the alternating sum is
This follows from the binomial theorem:
Every element in the union contributes one, and every element outside it contributes zero.
Indicator-function identity
An equivalent pointwise statement uses the indicator function , which equals one on and zero elsewhere:
Expanding the finite product gives
Summing over a finite universe proves the counting formula. Taking expectations or integrating proves the probability and measure versions. This explains why the principle is not confined to counting objects.
Probability and measure
For events in a probability space,
The left-hand side is the probability that at least one event occurs. The identity does not require independence. Independence only provides an additional way to evaluate intersection probabilities.
If the events are mutually independent, the complementary-event form simplifies to
Pairwise independence alone does not generally justify this product when there are three or more events.
In measure theory, the same alternating formula holds for measurable sets of finite measure. The finite-measure condition avoids undefined expressions involving subtraction of infinite quantities. More generally, integrating the indicator identity against an integrable weight yields weighted inclusion–exclusion.
Partial sums and Bonferroni inequalities
Calculating every intersection may be impractical. Truncating the alternating sum nevertheless gives rigorous bounds, called Bonferroni inequalities.
For events , define
and
For ,
The first two bounds are
The upper bound is commonly called the union bound. It underlies the Bonferroni correction used in multiple hypothesis testing.
The direction of the bounds follows element by element. For an outcome lying in exactly events, the truncated contribution is
where a binomial coefficient is zero when its lower index exceeds its nonnegative upper index. The error is nonnegative for odd and nonpositive for even . Analogous bounds hold for finite-set cardinalities and finite measures.
Counting exactly a specified number of properties
Inclusion–exclusion can also recover the number of objects belonging to exactly sets.
For subsets of a finite universe , let
If counts objects belonging to exactly of the sets, then
An object belonging to exactly sets contributes to . The alternating coefficients cancel this contribution unless , in which case it contributes one.
Applications
Permutations without fixed points
A derangement is a permutation with no fixed points. For permutations of objects, let consist of those fixing object . Fixing any specified objects leaves permutations, using the factorial notation.
Inclusion–exclusion gives the number of derangements:
Consequently,
where is Euler’s number. Thus the probability that a uniformly chosen permutation has no fixed points approaches .
Surjective functions
Consider functions from an -element set to an -element set, with . A surjective function uses every target value.
Let be the set of functions omitting target value . Omitting a specified collection of target values leaves functions. Therefore the number of surjections is
This equals times the number of partitions of the domain into nonempty blocks.
Divisibility and sieving
In number theory, take to be the integers from to divisible by a specified prime . For distinct primes,
The complement formula counts integers divisible by none of these primes. This is an elementary model of a sieve: unwanted objects are excluded through alternating corrections for overlapping divisibility conditions.
Graph coloring
For a finite simple graph , consider all assignments of colors to its vertices. For each edge, define a bad event in which its endpoints receive the same color.
If a collection of these equalities is imposed, all vertices in each connected component of must have one common color. There are such assignments, where includes isolated vertices.
Inclusion–exclusion therefore gives
For positive integers , this counts proper colorings. It also exhibits the count as a polynomial, called the chromatic polynomial, an important invariant in graph theory.
Algebraic interpretation
Inclusion–exclusion is a special case of Möbius inversion on the collection of subsets of a finite set, ordered by inclusion.
If functions and satisfy
then
The coefficient is the Möbius function of the subset order. This viewpoint places inclusion–exclusion within a broader theory of inverting cumulative sums on partially ordered sets.
Computational and infinite-family limitations
For sets, the full formula contains nonempty intersection terms. Direct evaluation therefore has exponential cost in the number of sets, even when each intersection count is readily available. Symmetry, empty intersections, or shared structure can reduce the work substantially.
The identity also requires higher-order overlap information. Individual set sizes and pairwise intersections generally do not determine a union when three or more sets are involved. Numerically, subtraction of large, nearly equal terms can cause loss of precision.
The finite identity should not be extended to an infinite alternating sum without checking convergence. For countably many events, a reliable formulation is
Each finite-union probability can be evaluated by inclusion–exclusion. Reorganizing the resulting limit into a series grouped by intersection order requires additional justification, such as suitable absolute-convergence conditions.