Inclusion–exclusion principle

Examples

Counting derangements

A more complex example is the following.

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

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

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

Each value ${\displaystyle A_{m_1}\cap \cdots \cap A_{m_p}}$ represents the set of shuffles having at least p values m₁, ..., m_p in the correct position. Note that the number of shuffles with at least p values correct only depends on p, not on the particular values of ${\displaystyle 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 n cards, 3 were chosen to be in the correct position. Thus there are $(\genfrac{}{}{0ex}{}{n}{p})$ equal terms in the p^th summation (see combination).

$${\displaystyle 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 }$$

${\displaystyle |A_1\cap \cdots \cap A_p|}$ is the number of orderings having p elements in the correct position, which is equal to the number of ways of ordering the remaining n − p elements, or (n − p)!. Thus we finally get: $${\displaystyle \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 n! to be the total number of permutations, the probability Q that a random shuffle produces a derangement is given by $${\displaystyle Q=1-\frac{W}{n!}=\sum _{p=0}^n\frac{(-1{)}^p}{p!},}$$ a truncation to n + 1 terms of the Taylor expansion of e⁻¹. Thus the probability of guessing an order for a shuffled deck of cards and being incorrect about every card is approximately e⁻¹ or 37%.

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 $${\displaystyle A_J:=\bigcap _{j\in J}{A}_j}$$ has the same cardinality, say α_k = |A_J|, for every k-element subset J of {1, ..., n}, then $${\displaystyle \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 S has cardinality α₀, $${\displaystyle \begin{array}{cc}\left|S\setminus \bigcup _{i=1}^n{A}_i\right|& ={\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 A₁, A₂, ..., A_n of a universal set S, the principle of inclusion–exclusion calculates the number of elements of S in none of these subsets. A generalization of this concept would calculate the number of elements of S which appear in exactly some fixed m of these sets.

Let N = [n] = {1, 2, ..., n}. If we define ${\displaystyle 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 S contained in none of the A_i is: $${\displaystyle \sum _{J\subseteq [n]}(-1{)}^{|J|}|A_J|.}$$

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

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

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

The correspondence K ↔ J = I ∪ K between subsets of N \ I and subsets of N containing I is a bijection and if J and K correspond under this map then B_K = A_J, showing that the result is valid.

In probability

In probability, for events A₁, ..., A_n in a probability space ${\displaystyle (\mathrm{\Omega },\mathcal{F},\mathbb{P})}$, the inclusion–exclusion principle becomes for n = 2 $${\displaystyle \mathbb{P}(A_1\cup A_2)=\mathbb{P}(A_1)+\mathbb{P}(A_2)-\mathbb{P}(A_1\cap A_2),}$$ for n = 3 $${\displaystyle \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 $${\displaystyle \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 $${\displaystyle \mathbb{P}\left(\bigcup _{i=1}^n{A}_i\right)=\sum _{k=1}^n\left((-1{)}^{k-1}\sum _{\genfrac{}{}{0ex}{}{I\subseteq \{1,\dots ,n\}}{|I|=k}}\mathbb{P}(A_I)\right),}$$ where the last sum runs over all subsets I of the indices 1, ..., n which contain exactly k elements, and $${\displaystyle A_I:=\bigcap _{i\in I}{A}_i}$$ denotes the intersection of all those A_i with index in I.

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 (S, Σ, μ) and measurable subsets A₁, ..., A_n of finite measure, the above identities also hold when the probability measure ${\displaystyle \mathbb{P}}$ is replaced by the measure μ.

Special case

If, in the probabilistic version of the inclusion–exclusion principle, the probability of the intersection A_I only depends on the cardinality of I, meaning that for every k in {1, ..., n} there is an a_k such that $${\displaystyle a_k=\mathbb{P}(A_I)\text{ for every }I\subset \{1,\dots ,n\}\text{ with }|I|=k,}$$ then the above formula simplifies to $${\displaystyle \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 ${\displaystyle A_i}$ are independent and identically distributed, then ${\displaystyle \mathbb{P}(A_i)=p}$ for all i, and we have ${\displaystyle a_k=p^k}$, in which case the expression above simplifies to $${\displaystyle \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 ${\displaystyle A_i}$.)

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

There is another formula used in point processes. Let ${\displaystyle S}$ be a finite set and ${\displaystyle P}$ be a random subset of ${\displaystyle S}$. Let ${\displaystyle A}$ be any subset of ${\displaystyle S}$, then $${\displaystyle \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 $${\displaystyle g(A)=\sum _{S\subseteq A}f(S)}$$ then

The combinatorial and the probabilistic version of the inclusion–exclusion principle are instances of (2).

Proof

Take ${\displaystyle \underset{\_}{m}=\{1,2,\dots ,m\}}$, ${\displaystyle f(\underset{\_}{m})=0}$, and $${\displaystyle f(S)=\left|\bigcap _{i\in \underset{\_}{m}\setminus S}{A}_i\setminus \bigcup _{i\in S}{A}_i\right|\text{ and }f(S)=\mathbb{P}\left(\bigcap _{i\in \underset{\_}{m}\setminus S}{A}_i\setminus \bigcup _{i\in S}{A}_i\right)}$$ respectively for all sets ${\displaystyle S}$ with ${\displaystyle S⊊\underset{\_}{m}}$. Then we obtain $${\displaystyle g(A)=\left|\bigcap _{i\in \underset{\_}{m}\setminus A}{A}_i\right|,g(\underset{\_}{m})=\left|\bigcup _{i\in \underset{\_}{m}}{A}_i\right|\text{ and }g(A)=\mathbb{P}\left(\bigcap _{i\in \underset{\_}{m}\setminus A}{A}_i\right),g(\underset{\_}{m})=\mathbb{P}\left(\bigcup _{i\in \underset{\_}{m}}{A}_i\right)}$$ respectively for all sets ${\displaystyle A}$ with ${\displaystyle A⊊\underset{\_}{m}}$. This is because elements ${\displaystyle a}$ of $\bigcap _{i\in \underset{\_}{m}\setminus A}{A}_i$ can be contained in other ${\displaystyle A_i}$ (${\displaystyle A_i}$ with ${\displaystyle i\in A}$) as well, and the $\bigcap \setminus \bigcup$-formula runs exactly through all possible extensions of the sets ${\displaystyle \{A_i\mid i\in \underset{\_}{m}\setminus A\}}$ with other ${\displaystyle A_i}$, counting ${\displaystyle a}$ only for the set that matches the membership behavior of ${\displaystyle a}$, if ${\displaystyle S}$ runs through all subsets of ${\displaystyle A}$ (as in the definition of ${\displaystyle g(A)}$).

Since ${\displaystyle f(\underset{\_}{m})=0}$, we obtain from (2) with ${\displaystyle A=\underset{\_}{m}}$ that $${\displaystyle \sum _{\underset{\_}{m}\supseteq T⊋\varnothing }(-1{)}^{|T|-1}g(\underset{\_}{m}\setminus T)=\sum _{\varnothing \subseteq S⊊\underset{\_}{m}}(-1{)}^{m-|S|-1}g(S)=g(\underset{\_}{m})}$$ and by interchanging sides, the combinatorial and the probabilistic version of the inclusion–exclusion principle follow.

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

For a generalization of the full version of Möbius inversion formula, (2) must be generalized to multisets. For multisets instead of sets, (2) becomes

where ${\displaystyle A-S}$ is the multiset for which ${\displaystyle (A-S)\uplus S=A}$, and

• μ(S) = 1 if S is a set (i.e. a multiset without double elements) of even cardinality.
• μ(S) = −1 if S is a set (i.e. a multiset without double elements) of odd cardinality.
• μ(S) = 0 if S is a proper multiset (i.e. S has double elements).

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

Proof of (3)

Substitute $${\displaystyle g(S)=\sum _{T\subseteq S}f(T)}$$ on the right hand side of (3). Notice that ${\displaystyle f(A)}$ appears once on both sides of (3). So we must show that for all ${\displaystyle T}$ with ${\displaystyle T⊊A}$, the terms ${\displaystyle f(T)}$ cancel out on the right hand side of (3). For that purpose, take a fixed ${\displaystyle T}$ such that ${\displaystyle T⊊A}$ and take an arbitrary fixed ${\displaystyle a\in A}$ such that ${\displaystyle a\notin T}$.

Notice that ${\displaystyle A-S}$ must be a set for each positive or negative appearance of ${\displaystyle f(T)}$ on the right hand side of (3) that is obtained by way of the multiset ${\displaystyle S}$ such that ${\displaystyle T\subseteq S\subseteq A}$. Now each appearance of ${\displaystyle f(T)}$ on the right hand side of (3) that is obtained by way of ${\displaystyle S}$ such that ${\displaystyle A-S}$ is a set that contains ${\displaystyle a}$ cancels out with the one that is obtained by way of the corresponding ${\displaystyle S}$ such that ${\displaystyle A-S}$ is a set that does not contain ${\displaystyle a}$. This gives the desired result.

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 A is a bijection from A into itself that has no fixed points. Via the inclusion–exclusion principle one can show that if the cardinality of A is n, then the number of derangements is [n! / e] where [x] denotes the nearest integer to x; 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: Essai d'analyse sur les jeux de hazard by P. R. de Montmort (1678 – 1719) and was known as either "Montmort's problem" or by the name he gave it, "problème des rencontres". The problem is also known as the hatcheck problem.

The number of derangements is also known as the subfactorial of n, written !n. It follows that if all bijections are assigned the same probability then the probability that a random bijection is a derangement quickly approaches 1/e as n 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 ${\displaystyle \overline{A_k}}$ represent the complement of A_k with respect to some universal set A such that ${\displaystyle A_k\subseteq A}$ for each k. Then we have $${\displaystyle \bigcap _{i=1}^n{A}_i=\overline{\bigcup _{i=1}^n\overline{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 A and B, how many surjective functions (onto functions) are there from A to B? Without any loss of generality we may take A = {1, ..., k} and B = {1, ..., n}, since only the cardinalities of the sets matter. By using S as the set of all functions from A to B, and defining, for each i in B, the property P_i as "the function misses the element i in B" (i is not in the image of the function), the principle of inclusion–exclusion gives the number of onto functions between A and B as: $${\displaystyle \sum _{j=0}^n(\genfrac{}{}{0ex}{}{n}{j})(-1{)}^j(n-j{)}^k.}$$

Permutations with forbidden positions

A permutation of the set S = {1, ..., n} where each element of S is restricted to not being in certain positions (here the permutation is considered as an ordering of the elements of S) is called a permutation with forbidden positions. For example, with S = {1,2,3,4}, 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 A_i be the set of positions that the element i is not allowed to be in, and the property P_i to be the property that a permutation puts element i into a position in A_i, 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 12 = 2(3!) permutations with property P₁, 6 = 3! permutations with property P₂, and no permutations have properties P₃ or P₄ as there are no restrictions for these two elements. The number of permutations satisfying the restrictions is thus: $${\displaystyle 4!-(12+6+0+0)+(4)=24-18+4=10.}$$

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

Stirling numbers of the second kind

The Stirling numbers of the second kind, S(n,k) count the number of partitions of a set of n elements into k 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 n-set into k non-empty but distinguishable boxes (ordered non-empty subsets). Using the universal set consisting of all partitions of the n-set into k (possibly empty) distinguishable boxes, A₁, A₂, ..., A_k, and the properties P_i meaning that the partition has box A_i empty, the principle of inclusion–exclusion gives an answer for the related result. Dividing by k! to remove the artificial ordering gives the Stirling number of the second kind: $${\displaystyle 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 B 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 B is any subset of the squares of a rectangular board with n rows and m columns; we think of it as the squares in which one is allowed to put a rook. The coefficient, r_k(B) of x^k in the rook polynomial R_B(x) is the number of ways k rooks, none of which attacks another, can be arranged in the squares of B. For any board B, there is a complementary board ${\displaystyle B^{\prime }}$ consisting of the squares of the rectangular board that are not in B. This complementary board also has a rook polynomial ${\displaystyle R_{B^{\prime }}(x)}$ with coefficients ${\displaystyle 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 n ≤ m, so this coefficient is r_n(B). The number of ways to place n non-attacking rooks on the complete n × m "checkerboard" (without regard as to whether the rooks are placed in the squares of the board B) is given by the falling factorial: $${\displaystyle (m{)}_n=m(m-1)(m-2)\cdots (m-n+1).}$$

Letting P_i be the property that an assignment of n non-attacking rooks on the complete board has a rook in column i which is not in a square of the board B, then by the principle of inclusion–exclusion we have: $${\displaystyle 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, φ(n) is an arithmetic function that counts the number of positive integers less than or equal to n that are relatively prime to n. That is, if n is a positive integer, then φ(n) is the number of integers k in the range 1 ≤ k ≤ n which have no common factor with n other than 1. The principle of inclusion–exclusion is used to obtain a formula for φ(n). Let S be the set {1, ..., n} and define the property P_i to be that a number in S is divisible by the prime number p_i, for 1 ≤ i ≤ r, where the prime factorization of $${\displaystyle n=p_1^{a_1}{p}_2^{a_2}\cdots p_r^{a_r}.}$$

Then, $${\displaystyle \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\left(1-\frac{1}{p_i}\right).}$$

Dirichlet hyperbola method

The Dirichlet hyperbola method re-expresses a sum of a multiplicative function ${\displaystyle f(n)}$ by selecting a suitable Dirichlet convolution ${\displaystyle f=g\ast h}$, recognizing that the sum $${\displaystyle 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 ${\displaystyle x\ge 1}$, ${\displaystyle y\ge 1}$, and ${\displaystyle xy\le n}$, splitting this region into two overlapping subregions, and finally using the inclusion–exclusion principle to conclude that $${\displaystyle 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 A₁, ..., A_n be arbitrary sets and p₁, ..., p_n real numbers in the closed unit interval [0, 1]. Then, for every even number k in {0, ..., n}, the indicator functions satisfy the inequality: $${\displaystyle {\mathbf{1}}_{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}{\mathbf{1}}_{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 ${\displaystyle A_1,A_2,\dots ,A_t}$ be the individual sets containing it. (Note that t > 0.) Since the element is counted precisely once by the left-hand side of equation (1), 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 ${\displaystyle 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: $${\displaystyle \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, $${\displaystyle 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 ${\displaystyle (\genfrac{}{}{0ex}{}{t}{0})=1}$ and rearranging terms, we have $${\displaystyle 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 (1).

Algebraic proof

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

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

Let A denote the union $\bigcup _{i=1}^n{A}_i$ of the sets A₁, ..., A_n. To prove the inclusion–exclusion principle in general, we first verify the identity

for indicator functions, where: $${\displaystyle A_I=\bigcap _{i\in I}{A}_i.}$$

The following function $${\displaystyle \left({\mathbf{1}}_A-{\mathbf{1}}_{A_1}\right)\left({\mathbf{1}}_A-{\mathbf{1}}_{A_2}\right)\cdots \left({\mathbf{1}}_A-{\mathbf{1}}_{A_n}\right)=0,}$$ is identically zero because: if x is not in A, then all factors are 0 − 0 = 0; and otherwise, if x does belong to some A_m, then the corresponding m^th factor is 1 − 1 = 0. By expanding the product on the left-hand side, equation (4) follows.

To prove the inclusion–exclusion principle for the cardinality of sets, sum the equation (4) over all x in the union of A₁, ..., A_n. To derive the version used in probability, take the expectation in (4). In general, integrate the equation (4) with respect to μ. Always use linearity in these derivations.