1 Statement of the principle
The inclusion–exclusion principle gives a way to compute the size of a union of finitely many sets (or the probability of that union in a finite sample space). The key idea is to correct for overlaps: if one simply sums sizes of individual sets, elements lying in multiple sets get counted too many times; alternating subtractions and additions using intersection sizes compensate for this systematic overcounting.
1.1 Two-set formula (baseline case)
For two sets \(A\) and \(B\), \[
| A\cup B | = | A | + | B | - | A\cap B | . |
|---|
\]
| The correction term \( | A\cap B | \) removes the elements counted in both sets, which would otherwise be double-counted in \( | A | + | B | \). |
|---|
1.2 Three-set formula (pattern of corrections)
For three sets \(A,B,C\), \[
| A\cup B\cup C | ||||||
|---|---|---|---|---|---|---|
| = | A | + | B | + | C | |
| -\bigl( | A\cap B | + | A\cap C | + | B\cap C | \bigr) |
| + | A\cap B\cap C | . |
\] Intersections of two sets are subtracted to remove double-counting, but elements belonging to all three sets were subtracted too often, so the triple intersection is added back.
1.3 General n-set formula (summation form)
For a finite family of sets \(A_1,\dots,A_n\), \[
| \left | \bigcup_{i=1}^n A_i\right |
|---|
=\sum_{k=1}^{n}(-1)^{k+1} \sum_{1\le i_1<\cdots<i_k\le n}
| \left | A_{i_1}\cap\cdots\cap A_{i_k}\right | . |
|---|
\] The outer sum runs over the number of sets intersecting; the sign alternates with \(k\). Each element that lies in exactly \(m\) of the sets contributes \(\sum_{k=1}^{m}(-1)^{k+1}\binom{m}{k}=1\), ensuring it is counted exactly once in the union.
1.4 Equivalent probability formulation (via finite sample spaces)
If \(\Omega\) is a finite sample space and \(A_i\subseteq \Omega\), then \[ \Pr\left(\bigcup_{i=1}^n A_i\right) =\sum_{k=1}^{n}(-1)^{k+1} \sum_{1\le i_1<\cdots<i_k\le n} \Pr\left(A_{i_1}\cap\cdots\cap A_{i_k}\right), \]
| because probabilities of events are just normalized cardinalities: \(\Pr(E)= | E | / | \Omega | \). |
|---|
2 Computing unions using intersections
In practice, inclusion–exclusion is most useful when the sizes of intersections of various subcollections of sets are accessible. The principle turns the problem of union counting into a structured computation over intersection counts.
2.1 Set cardinalities and direct counting
| When sets represent collections of objects satisfying properties, \( | A_i | \) counts objects with property \(i\), and \( | A_{i_1}\cap\cdots\cap A_{i_k} | \) counts objects satisfying all listed properties simultaneously. Inclusion–exclusion then yields the count of objects satisfying at least one property. |
|---|
2.2 Intersection sizes as prerequisites
A common workflow is:
1 Statement of the principle
2 Computing unions using intersections
3 Indicator variables and algebraic derivations
| If only \( | A_i | \) are known, the union size generally cannot be determined; intersection information is the missing ingredient. |
|---|
2.3 Handling empty intersections and simplifying terms
Many intersection terms are zero, either because properties are incompatible or because index combinations exceed feasibility. Terms with empty intersections can be dropped from the summation, reducing computation. Additionally, if intersection sizes depend only on how many sets are chosen (not which ones), the inner sum can be grouped, producing a shorter expression.
2.4 Worked example: counting with overlapping categories
| Suppose a survey outcome is an object characterized by whether it belongs to category \(A\), \(B\), or \(C\). Let \( | A | =50\), \( | B | =40\), \( | C | =30\), \( | A\cap B | =20\), \( | A\cap C | =10\), \( | B\cap C | =15\), and \( | A\cap B\cap C | =5\). Inclusion–exclusion gives |
|---|
\[
| A\cup B\cup C |
|---|
=50+40+30-(20+10+15)+5 =110. \] The result counts objects belonging to at least one category, correctly accounting for overlaps among categories.
3 Indicator variables and algebraic derivations
The principle admits algebraic derivations using indicator functions. This viewpoint clarifies why alternating sums of intersections arise naturally.
3.1 Indicator functions for membership
For a set \(A\), define the indicator function \( \mathbf{1}_A(x)\) by \[ \mathbf{1}_A(x)= \begin{cases} 1,& x\in A,\\ 0,& x\notin A. \end{cases} \] The union indicator is \(\mathbf{1}_{A_1\cup\cdots\cup A_n}(x)=\mathbf{1}\{\text{at least one }A_i\text{ contains }x\}\).
3.2 Deriving inclusion–exclusion via expansions
For each \(i\), the indicator of “not in \(A_i\)” is \(1-\mathbf{1}_{A_i}(x)\). Then \[ \mathbf{1}_{\cup_i A_i}(x) =1-\prod_{i=1}^n \bigl(1-\mathbf{1}_{A_i}(x)\bigr). \] Expanding the product yields alternating sums of products of indicators: \[ \prod_{i=1}^n (1-\mathbf{1}_{A_i}) =\sum_{k=0}^n (-1)^k \sum_{i_1<\cdots<i_k}\mathbf{1}_{A_{i_1}\cap\cdots\cap A_{i_k}}. \] After subtracting from 1 and summing over all \(x\) in the ground set, intersection cardinalities appear, producing the standard inclusion–exclusion formula.
3.3 Expectation form using linearity of expectation
On a finite probability space, let \(X\) be a random element distributed uniformly over \(\Omega\), and set \(E_i=\{X\in A_i\}\). Then \[ \mathbf{1}_{\cup_i A_i}(X) =1-\prod_{i=1}^n \bigl(1-\mathbf{1}_{A_i}(X)\bigr). \] Taking expectations and using the fact that expectation is linear transforms intersection indicator products into probabilities of intersections, giving the probabilistic inclusion–exclusion formula.
3.4 Relation to counting matchings and occupancy models (light applications)
Indicator-based derivations extend naturally to combinatorial counting models where each “constraint event” corresponds to an elementary indicator. For example, in occupancy problems where balls are placed into boxes, events might describe “a particular box gets no balls” or “a particular box exceeds a threshold.” Inclusion–exclusion then counts the configurations satisfying at least one of several listed constraints, or, by switching to complements, configurations avoiding them. While such applications vary in detail, the underlying algebra is consistent: unions of constraint events are handled by alternating intersection terms.
4 Common applications in combinatorics
In combinatorics, inclusion–exclusion frequently appears when counting objects under “at least one bad property” or “none of these bad properties” conditions. Complementary use is often the most convenient.
4.1 Counting functions with forbidden properties
Let \(F\) be the set of all functions from a finite domain to a finite codomain, and suppose certain properties are forbidden. Define \(A_i\) as the set of functions that violate condition \(i\). Then the number of acceptable functions is \[
| F | - \left | \bigcup_i A_i\right | . |
|---|
\]
| Inclusion–exclusion computes \(\left | \bigcup_i A_i\right | \) from intersection sizes of violations, yielding counts for configurations meeting all requirements simultaneously. |
|---|
4.2 Derangements and related exclusion counts
A derangement is a permutation with no fixed points. Let \(S_n\) be the symmetric group and let \(A_i\) be the set of permutations fixing position \(i\). Then the number of derangements equals the complement of permutations with at least one fixed point: \[
| !n = n! - | A_1\cup\cdots\cup A_n | . |
|---|
\]
| Inclusion–exclusion uses intersection sizes \( | A_{i_1}\cap\cdots\cap A_{i_k} | =(n-k)!\) to produce the classical count formula for derangements, with alternating sums that match the correction pattern of overcounting fixed points. |
|---|
4.3 Counting surjections (and complements via inclusion–exclusion)
Surjections from a set of size \(m\) to a set of size \(n\) can be counted by excluding missing values. Let \(A_i\) be the event that value \(i\) is not hit. Then functions that are not surjective lie in \(\cup_i A_i\), and \[ \#\{\text{surjections}\}
| = n^m - \left | \bigcup_{i=1}^n A_i\right | . |
|---|
\] Intersection sizes correspond to functions missing multiple values, and inclusion–exclusion converts those data into an alternating sum over binomial coefficients times powers.
4.4 Counting set systems with constraints
When counting collections that satisfy constraint patterns—such as families where certain elements must or must not appear—one often reduces the task to counting objects with particular “presence” or “absence” behaviors. Inclusion–exclusion then transforms constraints about existence (or avoidance) into sums involving intersections, which represent simultaneous satisfaction of multiple presence/absence conditions.
5 Variants and extensions
The principle generalizes beyond simple unweighted cardinalities and beyond the strict set-union formulation.
5.1 Multiset considerations (when repetitions matter)
With multisets, membership is not merely yes/no but can include multiplicities. Inclusion–exclusion can be adapted by representing multiplicity constraints with events defined on indicator variables for “at least \(t\) copies occur” or via generating-function interpretations. The central alternating-correction logic remains, but the event definitions must reflect how repeated occurrences interact.
5.2 Weighted inclusion–exclusion (sum over weights instead of counts)
If each element \(x\) carries a weight \(w(x)\), one can replace cardinalities with total weight over sets: \[ w(S)=\sum_{x\in S} w(x). \]
| Since the indicator-function derivation is algebraic, replacing \( | A | \) by \(w(A)\) yields an analogous formula: |
|---|
\[ w\left(\bigcup_i A_i\right)= \sum_{k=1}^n (-1)^{k+1} \sum_{i_1<\cdots<i_k} w(A_{i_1}\cap\cdots\cap A_{i_k}). \] This is useful in enumerative problems where weights reflect costs, sizes, or statistical weights.
5.3 Infinite variants for convergent cases (finite/infinite scope notes)
The standard statement assumes finitely many sets. For infinite families, inclusion–exclusion can still be meaningful under additional conditions, such as absolute convergence of the resulting series when interpreting the formula as a limit over finite subfamilies. Without such conditions, alternating sums may fail to converge or may not correspond to the desired union measure.
5.4 Inclusion–exclusion with symmetric structures (e.g., equal-size sets)
| When the underlying structure is symmetric, intersection sizes often depend only on how many sets are selected. Suppose \( | A_{i_1}\cap\cdots\cap A_{i_k} | \) depends only on \(k\). Then the inner sum over index choices reduces to a binomial coefficient factor: |
|---|
\[
| \left | \bigcup_{i=1}^n A_i\right |
|---|
=\sum_{k=1}^n (-1)^{k+1}\binom{n}{k}\,c_k, \] where \(c_k\) is the common value of the \(k\)-fold intersection size. This turns a potentially exponential enumeration of intersections into a manageable one-dimensional sum.
6 Computational considerations
Actual computation can be expensive because inclusion–exclusion involves many intersection terms.
6.1 Complexity in terms of number of sets
For \(n\) sets, the summation ranges over all nonempty subcollections, i.e., \(2^n-1\) intersection terms. Even if many are identical by symmetry, the naive approach scales exponentially with \(n\). The feasibility of a problem hinges on whether intersection sizes can be computed and aggregated efficiently.
6.2 Practical simplifications using symmetry
Symmetry frequently reduces workload. If intersections depend only on subset size or on a limited set of parameters, one can group terms and compute only a small set of distinct intersection sizes. Another simplification is to identify forced emptiness: incompatible property combinations produce zero intersections and remove entire blocks of terms.
6.3 Automating intersection enumeration (conceptual approach)
In algorithmic settings, one can automate inclusion–exclusion by systematically iterating over subsets of indices and computing intersection sizes via a separate counting subroutine. Conceptually, this corresponds to a subset-lattice traversal. In symbolic computation contexts, one often represents intersection sizes by formulas and lets algebra systems perform the alternating-sum aggregation.
6.4 Numerical stability and large coefficients (high-level notes)
When inclusion–exclusion is evaluated numerically, alternating sums can involve large intermediate values that cancel. This can lead to loss of precision in floating-point arithmetic. High-level strategies include exact arithmetic (integers/rationals), working with logarithms where appropriate, or using algebraic simplifications (such as combining symmetric terms) to reduce cancellation.
7 Connections to other concepts
Inclusion–exclusion sits within a broader framework of transforms on partially ordered sets and complements.
7.1 Möbius inversion on the subset lattice
Let \(f(S)\) be a function on subsets of \(\{1,\dots,n\}\) that records intersection sizes, and define \(g(T)\) as a related sum over supersets or subsets. Inclusion–exclusion corresponds to Möbius inversion on the Boolean lattice. The alternating binomial-type coefficients are precisely the Möbius function values for that lattice.
7.2 Zeta transform viewpoint (structural relationship)
The zeta transform converts a function by summing over subsets (or supersets). Inclusion–exclusion can be seen as the inverse operation of such a transform. In this sense, inclusion–exclusion provides the inversion formula that retrieves intersection-related data from union-related data, and vice versa.
7.3 Relation to the principle of counting by complements
Many applications use complements directly: counting objects with none of a family of “bad” properties. If bad-property sets are \(A_i\), then acceptable objects lie outside \(\cup_i A_i\). Because complements satisfy
| \( | F\setminus U | = | F | - | U | \), |
|---|
inclusion–exclusion for \(U\) becomes inclusion–exclusion for the complement.
7.4 Links to Euler characteristic–style alternation (intuition)
The alternating-sign structure resembles patterns found in topology and combinatorial geometry, where inclusion–exclusion-like alternations appear in formulas related to Euler characteristics. While inclusion–exclusion is fundamentally a counting identity, the shared “add, subtract, add … according to dimension of overlap” intuition often helps explain why alternating intersections naturally arise.
8 Proof strategies
Multiple proofs exist, each emphasizing a different viewpoint: overcounting correction, algebraic expansion, Möbius inversion, or induction.
8.1 Proof by overcounting and correction
A direct proof argues that each element \(x\) belonging to exactly \(m\) of the sets appears in the sum over single sets \(m\) times, then is subtracted when counting pairwise intersections, re-added for triple intersections, and so on. The alternating binomial sum \(\sum_{k=1}^m (-1)^{k+1}\binom{m}{k}=1\) shows that the net contribution of \(x\) to the final expression is exactly one, matching its presence in the union.
8.2 Proof via indicator expansion
Using the identity \[ \mathbf{1}_{\cup_i A_i}=1-\prod_{i=1}^n (1-\mathbf{1}_{A_i}), \] one expands the product, then sums over all elements to translate indicator products into intersection cardinalities. This proof is concise and highlights why alternating signs occur.
8.3 Möbius inversion proof outline
One can define a function on subsets of indices whose values are intersection sizes and then relate it to a function that sums over subfamilies. The inclusion–exclusion formula becomes the statement that the Möbius inversion operator on the Boolean lattice recovers one function from the other. The alternation corresponds to the Möbius function values.
8.4 Induction on the number of sets
Another route proves the formula for \(n=1\) and assumes it for \(n-1\). For the \(n\)th set, write \[
| \left | \bigcup_{i=1}^n A_i\right | |||||
|---|---|---|---|---|---|---|
| =\left | \bigcup_{i=1}^{n-1} A_i\right | + | A_n | -\left | A_n\cap \bigcup_{i=1}^{n-1} A_i\right | . |
\] The last term is handled by applying the induction hypothesis to intersections with \(A_n\), yielding the correct alternating pattern for all subset sizes.