Inclusion–exclusion principle

Venn diagram showing the union of sets Template:Mvar and Template:Mvar as everything not in white

In combinatorics, the inclusion–exclusion principle (commonly referred to as PIE) is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as $$|A\cup B|=|A|+|B|-|A\cap B|$$ where Template:Mvar and Template:Mvar are two finite sets and Template:Math indicates the cardinality of a set Template:Mvar (which may be considered as the number of elements of the set, if the set is finite). The formula expresses the fact that the sum of the sizes of the two sets may be too large since some elements may be counted twice. The double-counted elements are those in the intersection of the two sets and the count is corrected by subtracting the size of the intersection.

The inclusion-exclusion principle, being a generalization of the two-set case, is perhaps more clearly seen in the case of three sets, which for the sets Template:Mvar, Template:Mvar and Template:Mvar is given by $$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$$ This formula can be verified by counting how many times each region in the Venn diagram figure is included in the right-hand side of the formula. In this case, when removing the contributions of over-counted elements, the number of elements in the mutual intersection of the three sets has been subtracted too often, so must be added back in to get the correct total.

Inclusion–exclusion illustrated by a Venn diagram for three sets

Generalizing the results of these examples gives the principle of inclusion–exclusion. To find the cardinality of the union of Template:Mvar sets:

1. Include the cardinalities of the sets.
2. Exclude the cardinalities of the pairwise intersections.
3. Include the cardinalities of the triple-wise intersections.
4. Exclude the cardinalities of the quadruple-wise intersections.
5. Include the cardinalities of the quintuple-wise intersections.
6. Continue, until the cardinality of the Template:Mvar-tuple-wise intersection is included (if Template:Mvar is odd) or excluded (Template:Mvar even).

The name comes from the idea that the principle is based on over-generous inclusion, followed by compensating exclusion. This concept is attributed to Abraham de Moivre (1718), although it first appears in a paper of Daniel da Silva (1854) and later in a paper by J. J. Sylvester (1883). Sometimes the principle is referred to as the formula of Da Silva or Sylvester, due to these publications. The principle can be viewed as an example of the sieve method extensively used in number theory and is sometimes referred to as the sieve formula.

As finite probabilities are computed as counts relative to the cardinality of the probability space, the formulas for the principle of inclusion–exclusion remain valid when the cardinalities of the sets are replaced by finite probabilities. More generally, both versions of the principle can be put under the common umbrella of measure theory.

In a very abstract setting, the principle of inclusion–exclusion can be expressed as the calculation of the inverse of a certain matrix. This inverse has a special structure, making the principle an extremely valuable technique in combinatorics and related areas of mathematics. As Gian-Carlo Rota put it:Template:Sfn

"One of the most useful principles of enumeration in discrete probability and combinatorial theory is the celebrated principle of inclusion–exclusion. When skillfully applied, this principle has yielded the solution to many a combinatorial problem."

Formula

In its general formula, the principle of inclusion–exclusion states that for finite sets Template:Math, one has the identity Template:NumBlk

Each term of the inclusion–exclusion formula gradually corrects the count until finally each portion of the Venn diagram is counted exactly once.

This can be compactly written as $$\left|\bigcup _{i=1}^n{A}_i\right|=\sum _{k=1}^n(-1{)}^{k+1}\left(\sum _{1⩽i_1<\cdots <i_k⩽n}|A_{i_1}\cap \cdots \cap A_{i_k}|\right)$$ or $$\left|\bigcup _{i=1}^n{A}_i\right|=\sum _{\mathrm{\varnothing }\ne J\subseteq \{1,\dots ,n\}}(-1{)}^{|J|+1}\left|\bigcap _{j\in J}{A}_j\right|.$$

In words, to count the number of elements in a finite union of finite sets, first sum the cardinalities of the individual sets, then subtract the number of elements that appear in at least two sets, then add back the number of elements that appear in at least three sets, then subtract the number of elements that appear in at least four sets, and so on. This process always ends since there can be no elements that appear in more than the number of sets in the union. (For example, if $n=4,$ there can be no elements that appear in more than $4$ sets; equivalently, there can be no elements that appear in at least $5$ sets.)

In applications it is common to see the principle expressed in its complementary form. That is, letting Template:Mvar be a finite universal set containing all of the Template:Math and letting $\overline{A_i}$ denote the complement of Template:Math in Template:Mvar, by De Morgan's laws we have $$\left|\bigcap _{i=1}^n\overline{A_i}\right|=|S-\bigcup _{i=1}^n{A}_i|=|S|-\sum _{i=1}^n|A_i|+\sum _{1⩽i<j⩽n}|A_i\cap A_j|-\cdots +(-1{)}^n|A_1\cap \cdots \cap A_n|.$$

As another variant of the statement, let Template:Math be a list of properties that elements of a set Template:Mvar may or may not have, then the principle of inclusion–exclusion provides a way to calculate the number of elements of Template:Mvar that have none of the properties. Just let Template:Math be the subset of elements of Template:Mvar which have the property Template:Math and use the principle in its complementary form. This variant is due to J. J. Sylvester.

Notice that if you take into account only the first Template:Math sums on the right (in the general form of the principle), then you will get an overestimate if Template:Math is odd and an underestimate if Template:Math is even.

Examples

Counting derangements

A more complex example is the following.

Suppose there is a deck of Template:Mvar cards numbered from Template:Math to Template:Mvar. Suppose a card numbered Template:Mvar is in the correct position if it is the Template:Mvar^th card in the deck. How many ways, Template:Mvar, can the cards be shuffled with at least 1 card being in the correct position?

Begin by defining set Template:Math, which is all of the orderings of cards with the Template:Mvar^th card correct. Then the number of orders, Template:Mvar, with at least one card being in the correct position, Template:Mvar, is $$W=\left|\bigcup _{m=1}^n{A}_m\right|.$$

Apply the principle of inclusion–exclusion, $$W=\sum _{m_1=1}^n\left|A_{m_1}\right|-\sum _{1⩽m_1<m_2⩽n}|A_{m_1}\cap A_{m_2}|+\cdots +(-1{)}^{p-1}\sum _{1⩽m_1<\cdots <m_p⩽n}|A_{m_1}\cap \cdots \cap A_{m_p}|+\cdots$$

Each value $A_{m_1}\cap \cdots \cap A_{m_p}$ represents the set of shuffles having at least Template:Mvar values Template:Math in the correct position. Note that the number of shuffles with at least Template:Mvar values correct only depends on Template:Mvar, not on the particular values of $m$. For example, the number of shuffles having the 1st, 3rd, and 17th cards in the correct position is the same as the number of shuffles having the 2nd, 5th, and 13th cards in the correct positions. It only matters that of the Template:Mvar cards, 3 were chosen to be in the correct position. Thus there are $(\genfrac{}{}{0ex}{}{n}{p})$ equal terms in the Template:Mvar^th summation (see combination).

$$W=(\genfrac{}{}{0ex}{}{n}{1})|A_1|-(\genfrac{}{}{0ex}{}{n}{2})|A_1\cap A_2|+\cdots +(-1{)}^{p-1}(\genfrac{}{}{0ex}{}{n}{p})|A_1\cap \cdots \cap A_p|+\cdots$$

$|A_1\cap \cdots \cap A_p|$ is the number of orderings having Template:Mvar elements in the correct position, which is equal to the number of ways of ordering the remaining Template:Math elements, or Template:Math. Thus we finally get: $$\begin{array}{cc}W& =(\genfrac{}{}{0ex}{}{n}{1})(n-1)!-(\genfrac{}{}{0ex}{}{n}{2})(n-2)!+\cdots +(-1{)}^{p-1}(\genfrac{}{}{0ex}{}{n}{p})(n-p)!+\cdots \\ & =\sum _{p=1}^n(-1{)}^{p-1}(\genfrac{}{}{0ex}{}{n}{p})(n-p)!\\ & =\sum _{p=1}^n(-1{)}^{p-1}\frac{n!}{p!(n-p)!}(n-p)!\\ & =\sum _{p=1}^n(-1{)}^{p-1}\frac{n!}{p!}\end{array}$$

A permutation where no card is in the correct position is called a derangement. Taking Template:Math to be the total number of permutations, the probability Template:Mvar that a random shuffle produces a derangement is given by $$Q=1-\frac{W}{n!}=\sum _{p=0}^n\frac{(-1{)}^p}{p!},$$ a truncation to Template:Math terms of the Taylor expansion of Template:Math. Thus the probability of guessing an order for a shuffled deck of cards and being incorrect about every card is approximately Template:Math or Template:Math.

A special case

The situation that appears in the derangement example above occurs often enough to merit special attention. Namely, when the size of the intersection sets appearing in the formulas for the principle of inclusion–exclusion depend only on the number of sets in the intersections and not on which sets appear. More formally, if the intersection $$A_J:=\bigcap _{j\in J}{A}_j$$ has the same cardinality, say Template:Math, for every Template:Mvar-element subset Template:Mvar of Template:Math, then $$\left|\bigcup _{i=1}^n{A}_i\right|=\sum _{k=1}^n(-1{)}^{k-1}(\genfrac{}{}{0ex}{}{n}{k}){\alpha }_k.$$

Or, in the complementary form, where the universal set Template:Mvar has cardinality Template:Math, $$\begin{array}{cc}|S\setminus \bigcup _{i=1}^n{A}_i|& ={\alpha }_0-\sum _{k=1}^n(-1{)}^{k-1}(\genfrac{}{}{0ex}{}{n}{k}){\alpha }_k\\ & =\sum _{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k}){\alpha }_k.\end{array}$$

Formula generalization

Given a family (repeats allowed) of subsets Template:Math of a universal set Template:Mvar, the principle of inclusion–exclusion calculates the number of elements of Template:Mvar in none of these subsets. A generalization of this concept would calculate the number of elements of Template:Mvar which appear in exactly some fixed Template:Mvar of these sets.

Let Template:Math. If we define $A_{\mathrm{\varnothing }}=S$, then the principle of inclusion–exclusion can be written as, using the notation of the previous section; the number of elements of Template:Mvar contained in none of the Template:Math is: $$\sum _{J\subseteq [n]}(-1{)}^{|J|}|A_J|.$$

If Template:Mvar is a fixed subset of the index set Template:Mvar, then the number of elements which belong to Template:Math for all Template:Mvar in Template:Mvar and for no other values is: $$\sum _{J\supseteq I}(-1{)}^{|J|-|I|}|A_J|.$$

Define the sets $$B_k=A_{I\cup \{k\}}\text{ for }k\in N\setminus I.$$

We seek the number of elements in none of the Template:Math which, by the principle of inclusion–exclusion (with $B_{\mathrm{\varnothing }}=A_I$), is $$\sum _{K\subseteq N\setminus I}(-1{)}^{|K|}|B_K|.$$

The correspondence Template:Math between subsets of Template:Math and subsets of Template:Mvar containing Template:Mvar is a bijection and if Template:Mvar and Template:Mvar correspond under this map then Template:Mvar, showing that the result is valid.

In probability

In probability, for events Template:Math in a probability space $(\mathrm{\Omega },ℱ,\mathbb{P})$, the inclusion–exclusion principle becomes for Template:Math $$\mathbb{P}(A_1\cup A_2)=\mathbb{P}(A_1)+\mathbb{P}(A_2)-\mathbb{P}(A_1\cap A_2),$$ for Template:Math $$\mathbb{P}(A_1\cup A_2\cup A_3)=\mathbb{P}(A_1)+\mathbb{P}(A_2)+\mathbb{P}(A_3)-\mathbb{P}(A_1\cap A_2)-\mathbb{P}(A_1\cap A_3)-\mathbb{P}(A_2\cap A_3)+\mathbb{P}(A_1\cap A_2\cap A_3)$$ and in general $$\mathbb{P}\left(\bigcup _{i=1}^n{A}_i\right)=\sum _{i=1}^n\mathbb{P}(A_i)-\sum _{i<j}\mathbb{P}(A_i\cap A_j)+\sum _{i<j<k}\mathbb{P}(A_i\cap A_j\cap A_k)+\cdots +(-1{)}^{n-1}\mathbb{P}\left(\bigcap _{i=1}^n{A}_i\right),$$ which can be written in closed form as $$\mathbb{P}\left(\bigcup _{i=1}^n{A}_i\right)=\sum _{k=1}^n((-1{)}^{k-1}\sum _{\genfrac{}{}{0ex}{}{I\subseteq \{1,\dots ,n\}}{|I|=k}}\mathbb{P}(A_I)),$$ where the last sum runs over all subsets Template:Mvar of the indices Template:Math which contain exactly Template:Mvar elements, and $$A_I:=\bigcap _{i\in I}{A}_i$$ denotes the intersection of all those Template:Math with index in Template:Mvar.

According to the Bonferroni inequalities, the sum of the first terms in the formula is alternately an upper bound and a lower bound for the LHS. This can be used in cases where the full formula is too cumbersome.

For a general measure space Template:Math and measurable subsets Template:Math of finite measure, the above identities also hold when the probability measure $\mathbb{P}$ is replaced by the measure Template:Mvar.

Special case

If, in the probabilistic version of the inclusion–exclusion principle, the probability of the intersection Template:Math only depends on the cardinality of Template:Mvar, meaning that for every Template:Mvar in Template:Math there is an Template:Math such that $$a_k=\mathbb{P}(A_I)\text{ for every }I\subset \{1,\dots ,n\}\text{ with }|I|=k,$$ then the above formula simplifies to $$\mathbb{P}\left(\bigcup _{i=1}^n{A}_i\right)=\sum _{k=1}^n(-1{)}^{k-1}(\genfrac{}{}{0ex}{}{n}{k})a_k$$ due to the combinatorial interpretation of the binomial coefficient $(\genfrac{}{}{0ex}{}{n}{k})$. For example, if the events $A_i$ are independent and identically distributed, then $\mathbb{P}(A_i)=p$ for all Template:Mvar, and we have $a_k=p^k$, in which case the expression above simplifies to $$\mathbb{P}\left(\bigcup _{i=1}^n{A}_i\right)=1-(1-p{)}^n.$$

(This result can also be derived more simply by considering the intersection of the complements of the events $A_i$.)

An analogous simplification is possible in the case of a general measure space $(S,\mathrm{\Sigma },\mu )$ and measurable subsets $A_1,\dots ,A_n$ of finite measure.

There is another formula used in point processes. Let $S$ be a finite set and $P$ be a random subset of $S$. Let $A$ be any subset of $S$, then $$\begin{array}{cc}\mathbb{P}(P=A)& =\mathbb{P}(P\supset A)-\sum _{j_1\in S\setminus A}\mathbb{P}(P\supset A\cup j_1)\\ & \phantom{=}+\sum _{\genfrac{}{}{0ex}{}{j_1,j_2\in S\setminus A}{j_1\ne j_2}}\mathbb{P}(P\supset A\cup j_1,j_2)+\dots \\ & \phantom{=}+(-1{)}^{|S|-|A|}\mathbb{P}(P\supset S)\\ & =\sum _{A\subset J\subset S}(-1{)}^{|J|-|A|}\mathbb{P}(P\supset J).\end{array}$$

Other formulas

The principle is sometimes stated in the form that says that if $$g(A)=\sum _{S\subseteq A}f(S)$$ then Template:NumBlk

The combinatorial and the probabilistic version of the inclusion–exclusion principle are instances of (Template:EquationNote). Template:Math proof

If one sees a number $n$ as a set of its prime factors, then (Template:EquationNote) is a generalization of Möbius inversion formula for square-free natural numbers. Therefore, (Template:EquationNote) is seen as the Möbius inversion formula for the incidence algebra of the partially ordered set of all subsets of Template:Mvar.

For a generalization of the full version of Möbius inversion formula, (Template:EquationNote) must be generalized to multisets. For multisets instead of sets, (Template:EquationNote) becomes Template:NumBlk where $A-S$ is the multiset for which $(A-S)\uplus S=A$, and

• Template:Math if Template:Mvar is a set (i.e. a multiset without double elements) of even cardinality.
• Template:Math if Template:Mvar is a set (i.e. a multiset without double elements) of odd cardinality.
• Template:Math if Template:Mvar is a proper multiset (i.e. Template:Mvar has double elements).

Notice that $\mu (A-S)$ is just the $(-1{)}^{|A|-|S|}$ of (Template:EquationNote) in case $A-S$ is a set.

Applications

The inclusion–exclusion principle is widely used and only a few of its applications can be mentioned here.

Counting derangements

A well-known application of the inclusion–exclusion principle is to the combinatorial problem of counting all derangements of a finite set. A derangement of a set Template:Mvar is a bijection from Template:Mvar into itself that has no fixed points. Via the inclusion–exclusion principle one can show that if the cardinality of Template:Mvar is Template:Mvar, then the number of derangements is Template:Math where Template:Math denotes the nearest integer to Template:Mvar; a detailed proof is available here and also see the examples section above.

The first occurrence of the problem of counting the number of derangements is in an early book on games of chance: Template:Lang by P. R. de Montmort (1678 – 1719) and was known as either "Montmort's problem" or by the name he gave it, "Template:Lang". The problem is also known as the hatcheck problem.

The number of derangements is also known as the subfactorial of Template:Mvar, written Template:Math. It follows that if all bijections are assigned the same probability then the probability that a random bijection is a derangement quickly approaches Template:Math as Template:Mvar grows.

Counting intersections

The principle of inclusion–exclusion, combined with De Morgan's law, can be used to count the cardinality of the intersection of sets as well. Let $\overline{A_k}$ represent the complement of Template:Math with respect to some universal set Template:Mvar such that $A_k\subseteq A$ for each Template:Mvar. Then we have $$\bigcap _{i=1}^n{A}_i=\overline{\bigcup _{i=1}^n\stackrel{‾}{A_i}}$$ thereby turning the problem of finding an intersection into the problem of finding a union.

Graph coloring

The inclusion exclusion principle forms the basis of algorithms for a number of NP-hard graph partitioning problems, such as graph coloring.

A well known application of the principle is the construction of the chromatic polynomial of a graph.

Bipartite graph perfect matchings

The number of perfect matchings of a bipartite graph can be calculated using the principle.

Number of onto functions

Given finite sets Template:Mvar and Template:Mvar, how many surjective functions (onto functions) are there from Template:Mvar to Template:Mvar? Without any loss of generality we may take Template:Math and Template:Math, since only the cardinalities of the sets matter. By using Template:Mvar as the set of all functions from Template:Mvar to Template:Mvar, and defining, for each Template:Mvar in Template:Mvar, the property Template:Math as "the function misses the element Template:Mvar in Template:Mvar" (Template:Mvar is not in the image of the function), the principle of inclusion–exclusion gives the number of onto functions between Template:Mvar and Template:Mvar as: $$\sum _{j=0}^n(\genfrac{}{}{0ex}{}{n}{j})(-1{)}^j(n-j{)}^k.$$

Permutations with forbidden positions

A permutation of the set Template:Math where each element of Template:Mvar is restricted to not being in certain positions (here the permutation is considered as an ordering of the elements of Template:Mvar) is called a permutation with forbidden positions. For example, with Template:Math, the permutations with the restriction that the element 1 can not be in positions 1 or 3, and the element 2 can not be in position 4 are: 2134, 2143, 3124, 4123, 2341, 2431, 3241, 3421, 4231 and 4321. By letting Template:Math be the set of positions that the element Template:Mvar is not allowed to be in, and the property Template:Math to be the property that a permutation puts element Template:Mvar into a position in Template:Math, the principle of inclusion–exclusion can be used to count the number of permutations which satisfy all the restrictions.

In the given example, there are Template:Math permutations with property Template:Math, Template:Math permutations with property Template:Math, and no permutations have properties Template:Math or Template:Math as there are no restrictions for these two elements. The number of permutations satisfying the restrictions is thus: $$4!-(12+6+0+0)+(4)=24-18+4=10.$$

The final 4 in this computation is the number of permutations having both properties Template:Math and Template:Math. There are no other non-zero contributions to the formula.

Stirling numbers of the second kind

The Stirling numbers of the second kind, Template:Math count the number of partitions of a set of Template:Mvar elements into Template:Mvar non-empty subsets (indistinguishable boxes). An explicit formula for them can be obtained by applying the principle of inclusion–exclusion to a very closely related problem, namely, counting the number of partitions of an Template:Mvar-set into Template:Mvar non-empty but distinguishable boxes (ordered non-empty subsets). Using the universal set consisting of all partitions of the Template:Mvar-set into Template:Mvar (possibly empty) distinguishable boxes, Template:Math, and the properties Template:Math meaning that the partition has box Template:Math empty, the principle of inclusion–exclusion gives an answer for the related result. Dividing by Template:Math to remove the artificial ordering gives the Stirling number of the second kind: $$S(n,k)=\frac{1}{k!}\sum _{t=0}^k(-1{)}^t(\genfrac{}{}{0ex}{}{k}{t})(k-t{)}^n.$$

Rook polynomials

A rook polynomial is the generating function of the number of ways to place non-attacking rooks on a board Template:Mvar that looks like a subset of the squares of a checkerboard; that is, no two rooks may be in the same row or column. The board Template:Mvar is any subset of the squares of a rectangular board with Template:Mvar rows and Template:Mvar columns; we think of it as the squares in which one is allowed to put a rook. The coefficient, Template:Math of Template:Math in the rook polynomial Template:Math is the number of ways Template:Mvar rooks, none of which attacks another, can be arranged in the squares of Template:Mvar. For any board Template:Mvar, there is a complementary board $B^{\prime }$ consisting of the squares of the rectangular board that are not in Template:Mvar. This complementary board also has a rook polynomial $R_{B^{\prime }}(x)$ with coefficients $r_k(B^{\prime }).$

It is sometimes convenient to be able to calculate the highest coefficient of a rook polynomial in terms of the coefficients of the rook polynomial of the complementary board. Without loss of generality we can assume that Template:Math, so this coefficient is Template:Math. The number of ways to place Template:Mvar non-attacking rooks on the complete Template:Math "checkerboard" (without regard as to whether the rooks are placed in the squares of the board Template:Mvar) is given by the falling factorial: $$(m{)}_n=m(m-1)(m-2)\cdots (m-n+1).$$

Letting Template:Math be the property that an assignment of Template:Mvar non-attacking rooks on the complete board has a rook in column Template:Mvar which is not in a square of the board Template:Mvar, then by the principle of inclusion–exclusion we have: $$r_n(B)=\sum _{t=0}^n(-1{)}^t(m-t{)}_{n-t}{r}_t(B^{\prime }).$$

Euler's phi function

Euler's totient or phi function, Template:Math is an arithmetic function that counts the number of positive integers less than or equal to Template:Mvar that are relatively prime to Template:Mvar. That is, if Template:Mvar is a positive integer, then Template:Math is the number of integers Template:Mvar in the range Template:Math which have no common factor with Template:Mvar other than 1. The principle of inclusion–exclusion is used to obtain a formula for Template:Math. Let Template:Mvar be the set Template:Math and define the property Template:Math to be that a number in Template:Mvar is divisible by the prime number Template:Math, for Template:Math, where the prime factorization of $$n=p_1^{a_1}{p}_2^{a_2}\cdots p_r^{a_r}.$$

Then, $$\phi (n)=n-\sum _{i=1}^r\frac{n}{p_i}+\sum _{1⩽i<j⩽r}\frac{n}{p_i{p}_j}-\cdots =n\prod _{i=1}^r(1-\frac{1}{p_i}).$$

Dirichlet hyperbola method

An example of the Dirichlet hyperbola method with Template:Math, Template:Math, and Template:Math.

The Dirichlet hyperbola method re-expresses a sum of a multiplicative function $f(n)$ by selecting a suitable Dirichlet convolution $f=g\ast h$, recognizing that the sum $$F(n)=\sum _{k=1}^{n}f(k)=\sum _{k=1}^n\sum _{xy=k}^{}g(x)h(y)$$ can be recast as a sum over the lattice points in a region bounded by $x\ge 1$, $y\ge 1$, and $xy\le n$, splitting this region into two overlapping subregions, and finally using the inclusion–exclusion principle to conclude that $$F(n)=\sum _{k=1}^{n}f(k)=\sum _{k=1}^n\sum _{xy=k}^{}g(x)h(y)=\sum _{x=1}^a\sum _{y=1}^{n/x}g(x)h(y)+\sum _{y=1}^b\sum _{x=1}^{n/y}g(x)h(y)-\sum _{x=1}^a\sum _{y=1}^{b}g(x)h(y).$$

Diluted inclusion–exclusion principle

In many cases where the principle could give an exact formula (in particular, counting prime numbers using the sieve of Eratosthenes), the formula arising does not offer useful content because the number of terms in it is excessive. If each term individually can be estimated accurately, the accumulation of errors may imply that the inclusion–exclusion formula is not directly applicable. In number theory, this difficulty was addressed by Viggo Brun. After a slow start, his ideas were taken up by others, and a large variety of sieve methods developed. These for example may try to find upper bounds for the "sieved" sets, rather than an exact formula.

Let Template:Math be arbitrary sets and Template:Math real numbers in the closed unit interval Template:Closed-closed. Then, for every even number Template:Mvar in Template:Math, the indicator functions satisfy the inequality: $${\mathrm{𝟏}}_{A_1\cup \cdots \cup A_n}\ge \sum _{j=1}^k(-1{)}^{j-1}\sum _{1\le i_1<\cdots <i_j\le n}{p}_{i_1}\dots p_{i_j}{\mathrm{𝟏}}_{A_{i_1}\cap \cdots \cap A_{i_j}}.$$

Proof of main statement

Choose an element contained in the union of all sets and let $A_1,A_2,\dots ,A_t$ be the individual sets containing it. (Note that Template:Math.) Since the element is counted precisely once by the left-hand side of equation (Template:EquationNote), we need to show that it is counted precisely once by the right-hand side. On the right-hand side, the only non-zero contributions occur when all the subsets in a particular term contain the chosen element, that is, all the subsets are selected from $A_1,A_2,\dots ,A_t$. The contribution is one for each of these sets (plus or minus depending on the term) and therefore is just the (signed) number of these subsets used in the term. We then have: $$\begin{array}{cc}|\{A_i\mid 1⩽i⩽t\}|& -|\{A_i\cap A_j\mid 1⩽i<j⩽t\}|+\cdots +(-1{)}^{t+1}|\{A_1\cap A_2\cap \cdots \cap A_t\}|=(\genfrac{}{}{0ex}{}{t}{1})-(\genfrac{}{}{0ex}{}{t}{2})+\cdots +(-1{)}^{t+1}(\genfrac{}{}{0ex}{}{t}{t}).\end{array}$$

By the binomial theorem, $$0=(1-1{)}^t=(\genfrac{}{}{0ex}{}{t}{0})-(\genfrac{}{}{0ex}{}{t}{1})+(\genfrac{}{}{0ex}{}{t}{2})-\cdots +(-1{)}^t(\genfrac{}{}{0ex}{}{t}{t}).$$

Using the fact that $(\genfrac{}{}{0ex}{}{t}{0})=1$ and rearranging terms, we have $$1=(\genfrac{}{}{0ex}{}{t}{1})-(\genfrac{}{}{0ex}{}{t}{2})+\cdots +(-1{)}^{t+1}(\genfrac{}{}{0ex}{}{t}{t}),$$ and so, the chosen element is counted only once by the right-hand side of equation (Template:EquationNote).

Algebraic proof

An algebraic proof can be obtained using indicator functions (also known as characteristic functions). The indicator function of a subset Template:Mvar of a set Template:Mvar is the function $$\begin{array}{cc}& {\mathrm{𝟏}}_S:X\to \{0,1\}\\ & {\mathrm{𝟏}}_S(x)=\{\begin{array}{cc}1& x\in S\\ 0& x\notin S\end{array}\end{array}$$

If $A$ and $B$ are two subsets of $X$, then $${\mathrm{𝟏}}_A\cdot {\mathrm{𝟏}}_B={\mathrm{𝟏}}_{A\cap B}.$$

Let Template:Mvar denote the union ${\bigcup }_{i=1}^n{A}_i$ of the sets Template:Math. To prove the inclusion–exclusion principle in general, we first verify the identity Template:NumBlk for indicator functions, where: $$A_I=\bigcap _{i\in I}{A}_i.$$

The following function $$({\mathrm{𝟏}}_A-{\mathrm{𝟏}}_{A_1})({\mathrm{𝟏}}_A-{\mathrm{𝟏}}_{A_2})\cdots ({\mathrm{𝟏}}_A-{\mathrm{𝟏}}_{A_n})=0,$$ is identically zero because: if Template:Mvar is not in Template:Mvar, then all factors are Template:Math; and otherwise, if Template:Mvar does belong to some Template:Math, then the corresponding Template:Mvar^th factor is Template:Math. By expanding the product on the left-hand side, equation (Template:EquationNote) follows.

To prove the inclusion–exclusion principle for the cardinality of sets, sum the equation (Template:EquationNote) over all Template:Mvar in the union of Template:Math. To derive the version used in probability, take the expectation in (Template:EquationNote). In general, integrate the equation (Template:EquationNote) with respect to Template:Mvar. Always use linearity in these derivations.

See also

• Template:Annotated link
• Template:Annotated link
• Template:Annotated link
• Template:Annotated link
• Template:Annotated link
• Template:Annotated link

References

• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Springer
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation