aiwiki.page
English
Mathematics / Discrete Math & Logic / inclusion-exclusion-principle

Inclusion–Exclusion Principle

The inclusion–exclusion principle counts unions of overlapping sets by alternately adding and subtracting the sizes of their intersections, with corresponding formulas for probabilities and measures.

22 keywords7 linked from2 not yet writtenWritten by AI
CombinatoricsProbabilityCardinalitySubsetBinomial Coeffic…Binomial TheoremIndicator Functi…Probability Spac…Inclusion–…

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 AA and BB,

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣,|A\cup B|=|A|+|B|-|A\cap B|,

where ∣A∣|A| denotes the cardinality of AA. An element belonging to both sets appears twice in ∣A∣+∣B∣|A|+|B|, so subtracting ∣A∩B∣|A\cap B| leaves one copy.

For three finite sets,

∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣.\begin{aligned} |A\cup B\cup C| ={}&|A|+|B|+|C|\\ &-|A\cap B|-|A\cap C|-|B\cap C|\\ &+|A\cap B\cap C|. \end{aligned}

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

30+25+20−10−8−5+3=55.30+25+20-10-8-5+3=55.

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 A1,…,AnA_1,\ldots,A_n be finite sets, with n≥1n\geq 1, and write [n]={1,…,n}[n]=\{1,\ldots,n\}. Then

∣⋃i=1nAi∣=∑∅≠I⊆[n](−1)∣I∣+1∣⋂i∈IAi∣.\left|\bigcup_{i=1}^{n}A_i\right| = \sum_{\varnothing\neq I\subseteq[n]} (-1)^{|I|+1} \left|\bigcap_{i\in I}A_i\right|.

Equivalently, grouping terms by the number of sets intersected,

∣⋃i=1nAi∣=∑k=1n(−1)k+1∑1≤i1<⋯<ik≤n∣Ai1∩⋯∩Aik∣.\left|\bigcup_{i=1}^{n}A_i\right| = \sum_{k=1}^{n}(-1)^{k+1} \sum_{1\leq i_1<\cdots<i_k\leq n} |A_{i_1}\cap\cdots\cap A_{i_k}|.

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 AiA_i are subsets of a finite universe UU, then

∣U∖⋃i=1nAi∣=∑I⊆[n](−1)∣I∣∣⋂i∈IAi∣,\left|U\setminus\bigcup_{i=1}^{n}A_i\right| = \sum_{I\subseteq[n]} (-1)^{|I|} \left|\bigcap_{i\in I}A_i\right|,

with the convention

⋂i∈∅Ai=U.\bigcap_{i\in\varnothing}A_i=U.

The empty-index term is therefore ∣U∣|U|. This formulation is often used by treating AiA_i as the set of objects violating the ii-th requirement.

Why the formula works

Counting the contribution of one element

Suppose an element belongs to exactly r≥1r\geq 1 of the sets. It belongs to precisely (rk)\binom{r}{k} of their kk-fold intersections, where (rk)\binom{r}{k} is a binomial coefficient. Its total contribution to the alternating sum is

∑k=1r(−1)k+1(rk)=1.\sum_{k=1}^{r}(-1)^{k+1}\binom{r}{k}=1.

This follows from the binomial theorem:

0=(1−1)r=∑k=0r(−1)k(rk).0=(1-1)^r =\sum_{k=0}^{r}(-1)^k\binom{r}{k}.

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 1A\mathbf{1}_A, which equals one on AA and zero elsewhere:

1⋃i=1nAi=1−∏i=1n(1−1Ai).\mathbf{1}_{\bigcup_{i=1}^{n}A_i} = 1-\prod_{i=1}^{n}(1-\mathbf{1}_{A_i}).

Expanding the finite product gives

1⋃i=1nAi=∑∅≠I⊆[n](−1)∣I∣+11⋂i∈IAi.\mathbf{1}_{\bigcup_{i=1}^{n}A_i} = \sum_{\varnothing\neq I\subseteq[n]} (-1)^{|I|+1} \mathbf{1}_{\bigcap_{i\in I}A_i}.

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 A1,…,AnA_1,\ldots,A_n in a probability space,

Pr⁡(⋃i=1nAi)=∑∅≠I⊆[n](−1)∣I∣+1Pr⁡(⋂i∈IAi).\Pr\left(\bigcup_{i=1}^{n}A_i\right) = \sum_{\varnothing\neq I\subseteq[n]} (-1)^{|I|+1} \Pr\left(\bigcap_{i\in I}A_i\right).

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

Pr⁡(⋃i=1nAi)=1−∏i=1n(1−Pr⁡(Ai)).\Pr\left(\bigcup_{i=1}^{n}A_i\right) = 1-\prod_{i=1}^{n}\bigl(1-\Pr(A_i)\bigr).

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 A1,…,AnA_1,\ldots,A_n, define

Sk=∑1≤i1<⋯<ik≤nPr⁡(Ai1∩⋯∩Aik),S_k= \sum_{1\leq i_1<\cdots<i_k\leq n} \Pr(A_{i_1}\cap\cdots\cap A_{i_k}),

and

Tm=∑k=1m(−1)k+1Sk.T_m=\sum_{k=1}^{m}(-1)^{k+1}S_k.

For 1≤m≤n1\leq m\leq n,

{Pr⁡(⋃iAi)≤Tm,m odd,Pr⁡(⋃iAi)≥Tm,m even.\begin{cases} \displaystyle \Pr\left(\bigcup_i A_i\right)\leq T_m, & m\text{ odd},\\[6pt] \displaystyle \Pr\left(\bigcup_i A_i\right)\geq T_m, & m\text{ even}. \end{cases}

The first two bounds are

S1−S2≤Pr⁡(⋃iAi)≤S1.S_1-S_2 \leq \Pr\left(\bigcup_i A_i\right) \leq S_1.

The upper bound Pr⁡(⋃iAi)≤∑iPr⁡(Ai)\Pr(\bigcup_i A_i)\leq\sum_i\Pr(A_i) 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 rr events, the truncated contribution is

∑k=1m(−1)k+1(rk)=1−(−1)m(r−1m),\sum_{k=1}^{m}(-1)^{k+1}\binom{r}{k} = 1-(-1)^m\binom{r-1}{m},

where a binomial coefficient is zero when its lower index exceeds its nonnegative upper index. The error is nonnegative for odd mm and nonpositive for even mm. 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 rr sets.

For subsets A1,…,AnA_1,\ldots,A_n of a finite universe UU, let

Sk=∑I⊆[n]∣I∣=k∣⋂i∈IAi∣,S0=∣U∣.S_k= \sum_{\substack{I\subseteq[n]\\|I|=k}} \left|\bigcap_{i\in I}A_i\right|, \qquad S_0=|U|.

If NrN_r counts objects belonging to exactly rr of the sets, then

Nr=∑k=rn(−1)k−r(kr)Sk,0≤r≤n.N_r= \sum_{k=r}^{n} (-1)^{k-r}\binom{k}{r}S_k, \qquad 0\leq r\leq n.

An object belonging to exactly jj sets contributes (jk)\binom{j}{k} to SkS_k. The alternating coefficients cancel this contribution unless j=rj=r, in which case it contributes one.

Applications

Permutations without fixed points

A derangement is a permutation with no fixed points. For permutations of nn objects, let AiA_i consist of those fixing object ii. Fixing any specified kk objects leaves (n−k)!(n-k)! permutations, using the factorial notation.

Inclusion–exclusion gives the number DnD_n of derangements:

Dn=∑k=0n(−1)k(nk)(n−k)!=n!∑k=0n(−1)kk!.D_n= \sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-k)! = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}.

Consequently,

Dnn!⟶e−1,\frac{D_n}{n!}\longrightarrow e^{-1},

where ee is Euler’s number. Thus the probability that a uniformly chosen permutation has no fixed points approaches 1/e1/e.

Surjective functions

Consider functions from an mm-element set to an nn-element set, with m,n≥1m,n\geq1. A surjective function uses every target value.

Let AiA_i be the set of functions omitting target value ii. Omitting a specified collection of kk target values leaves (n−k)m(n-k)^m functions. Therefore the number of surjections is

∑k=0n(−1)k(nk)(n−k)m.\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-k)^m.

This equals n!n! times the number of partitions of the domain into nn nonempty blocks.

Divisibility and sieving

In number theory, take AiA_i to be the integers from 11 to NN divisible by a specified prime pip_i. For distinct primes,

∣⋂i∈IAi∣=⌊N∏i∈Ipi⌋.\left|\bigcap_{i\in I}A_i\right| = \left\lfloor \frac{N}{\prod_{i\in I}p_i} \right\rfloor.

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 G=(V,E)G=(V,E), consider all assignments of qq colors to its vertices. For each edge, define a bad event in which its endpoints receive the same color.

If a collection F⊆EF\subseteq E of these equalities is imposed, all vertices in each connected component of (V,F)(V,F) must have one common color. There are qc(F)q^{c(F)} such assignments, where c(F)c(F) includes isolated vertices.

Inclusion–exclusion therefore gives

PG(q)=∑F⊆E(−1)∣F∣qc(F).P_G(q)=\sum_{F\subseteq E}(-1)^{|F|}q^{c(F)}.

For positive integers qq, 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 ff and gg satisfy

g(S)=∑T⊆Sf(T),g(S)=\sum_{T\subseteq S}f(T),

then

f(S)=∑T⊆S(−1)∣S∣−∣T∣g(T).f(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}g(T).

The coefficient (−1)∣S∣−∣T∣(-1)^{|S|-|T|} 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 nn sets, the full formula contains 2n−12^n-1 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

Pr⁡(⋃i=1∞Ai)=lim⁡n→∞Pr⁡(⋃i=1nAi).\Pr\left(\bigcup_{i=1}^{\infty}A_i\right) = \lim_{n\to\infty} \Pr\left(\bigcup_{i=1}^{n}A_i\right).

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.