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 ∪ B | = | A | + | B | − | A ∩ B | {\displaystyle |A\cup B|=|A|+|B|-|A\cap B|}
where A and B are two finite sets and |S| indicates the cardinality of a set S (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 A, B and C is given by
| A ∪ B ∪ C | = | A | + | B | + | C | − | A ∩ B | − | A ∩ C | − | B ∩ C | + | A ∩ B ∩ C | {\displaystyle |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.
Generalizing the results of these examples gives the principle of inclusion–exclusion. To find the cardinality of the union of n sets:
Include the cardinalities of the sets. Exclude the cardinalities of the pairwise intersections. Include the cardinalities of the triple-wise intersections. Exclude the cardinalities of the quadruple-wise intersections. Include the cardinalities of the quintuple-wise intersections. Continue, until the cardinality of the n-tuple-wise intersection is included (if n is odd) or excluded (n 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:
"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 A1, ..., An, one has the identity
This can be compactly written as
| ⋃ i = 1 n A i | = ∑ k = 1 n ( − 1 ) k + 1 ( ∑ 1 ⩽ i 1 < ⋯ < i k ⩽ n | A i 1 ∩ ⋯ ∩ A i k | ) {\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{k=1}^{n}(-1)^{k+1}\left(\sum _{1\leqslant i_{1}<\cdots <i_{k}\leqslant n}\left|A_{i_{1}}\cap \cdots \cap A_{i_{k}}\right|\right)}
or
| ⋃ i = 1 n A i | = ∑ ∅ ≠ J ⊆ { 1 , … , n } ( − 1 ) | J | + 1 | ⋂ j ∈ J A j | . {\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{\emptyset \neq J\subseteq \{1,\ldots ,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 , {\displaystyle n=4,} there can be no elements that appear in more than 4 {\displaystyle 4} sets; equivalently, there can be no elements that appear in at least 5 {\displaystyle 5} sets.) In applications it is common to see the principle expressed in its complementary form. That is, letting S be a finite universal set containing all of the Ai and letting A i ¯ {\displaystyle {\overline {A_{i}}}} denote the complement of Ai in S, by De Morgan's laws we have
| ⋂ i = 1 n A i ¯ | = | S − ⋃ i = 1 n A i | = | S | − ∑ i = 1 n | A i | + ∑ 1 ⩽ i < j ⩽ n | A i ∩ A j | − ⋯ + ( − 1 ) n | A 1 ∩ ⋯ ∩ A n | . {\displaystyle \left|\bigcap _{i=1}^{n}{\overline {A_{i}}}\right|=\left|S-\bigcup _{i=1}^{n}A_{i}\right|=|S|-\sum _{i=1}^{n}|A_{i}|+\sum _{1\leqslant i<j\leqslant n}|A_{i}\cap A_{j}|-\cdots +(-1)^{n}|A_{1}\cap \cdots \cap A_{n}|.}
As another variant of the statement, let P1, ..., Pn be a list of properties that elements of a set S may or may not have, then the principle of inclusion–exclusion provides a way to calculate the number of elements of S that have none of the properties. Just let Ai be the subset of elements of S which have the property Pi 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 m<n sums on the right (in the general form of the principle), then you will get an overestimate if m is odd and an underestimate if m is even.
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 mth 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 Am, which is all of the orderings of cards with the mth card correct. Then the number of orders, W, with at least one card being in the correct position, m, is
W = | ⋃ m = 1 n A m | . {\displaystyle W=\left|\bigcup _{m=1}^{n}A_{m}\right|.}
Apply the principle of inclusion–exclusion,
W = ∑ m 1 = 1 n | A m 1 | − ∑ 1 ⩽ m 1 < m 2 ⩽ n | A m 1 ∩ A m 2 | + ⋯ + ( − 1 ) p − 1 ∑ 1 ⩽ m 1 < ⋯ < m p ⩽ n | A m 1 ∩ ⋯ ∩ A m p | + ⋯ {\displaystyle W=\sum _{m_{1}=1}^{n}\left|A_{m_{1}}\right|-\sum _{1\leqslant m_{1}<m_{2}\leqslant n}\left|A_{m_{1}}\cap A_{m_{2}}\right|+\cdots +(-1)^{p-1}\sum _{1\leqslant m_{1}<\cdots <m_{p}\leqslant n}\left|A_{m_{1}}\cap \cdots \cap A_{m_{p}}\right|+\cdots }
Each value A m 1 ∩ ⋯ ∩ A m p {\displaystyle A_{m_{1}}\cap \cdots \cap A_{m_{p}}} represents the set of shuffles having at least p values m1, ..., mp 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 m {\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 ( n p ) {\textstyle {n \choose p}} equal terms in the pth summation (see combination).
W = ( n 1 ) | A 1 | − ( n 2 ) | A 1 ∩ A 2 | + ⋯ + ( − 1 ) p − 1 ( n p ) | A 1 ∩ ⋯ ∩ A p | + ⋯ {\displaystyle W={n \choose 1}|A_{1}|-{n \choose 2}|A_{1}\cap A_{2}|+\cdots +(-1)^{p-1}{n \choose p}|A_{1}\cap \cdots \cap A_{p}|+\cdots }
| A 1 ∩ ⋯ ∩ A p | {\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:
W = ( n 1 ) ( n − 1 ) ! − ( n 2 ) ( n − 2 ) ! + ⋯ + ( − 1 ) p − 1 ( n p ) ( n − p ) ! + ⋯ = ∑ p = 1 n ( − 1 ) p − 1 ( n p ) ( n − p ) ! = ∑ p = 1 n ( − 1 ) p − 1 n ! p ! ( n − p ) ! ( n − p ) ! = ∑ p = 1 n ( − 1 ) p − 1 n ! p ! {\displaystyle {\begin{aligned}W&={n \choose 1}(n-1)!-{n \choose 2}(n-2)!+\cdots +(-1)^{p-1}{n \choose p}(n-p)!+\cdots \\&=\sum _{p=1}^{n}(-1)^{p-1}{n \choose 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{aligned}}}
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
Q = 1 − W n ! = ∑ p = 0 n ( − 1 ) p p ! , {\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−1. Thus the probability of guessing an order for a shuffled deck of cards and being incorrect about every card is approximately e−1 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
A J := ⋂ j ∈ J A j {\displaystyle A_{J}:=\bigcap _{j\in J}A_{j}}
has the same cardinality, say αk = |AJ|, for every k-element subset J of {1, ..., n}, then
| ⋃ i = 1 n A i | = ∑ k = 1 n ( − 1 ) k − 1 ( n k ) α k . {\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{k=1}^{n}(-1)^{k-1}{\binom {n}{k}}\alpha _{k}.}
Or, in the complementary form, where the universal set S has cardinality α0,
| S ∖ ⋃ i = 1 n A i | = α 0 − ∑ k = 1 n ( − 1 ) k − 1 ( n k ) α k = ∑ k = 0 n ( − 1 ) k ( n k ) α k . {\displaystyle {\begin{aligned}\left|S\smallsetminus \bigcup _{i=1}^{n}A_{i}\right|&=\alpha _{0}-\sum _{k=1}^{n}(-1)^{k-1}{\binom {n}{k}}\alpha _{k}\\&=\sum _{k=0}^{n}(-1)^{k}{\binom {n}{k}}\alpha _{k}.\end{aligned}}}
Formula generalization Given a family (repeats allowed) of subsets A1, A2, ..., An 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 A ∅ = S {\displaystyle A_{\emptyset }=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 Ai is:
∑ J ⊆ [ n ] ( − 1 ) | J | | A J | . {\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 Ai for all i in I and for no other values is:
∑ J ⊇ I ( − 1 ) | J | − | I | | A J | . {\displaystyle \sum _{J\supseteq I}(-1)^{|J|-|I|}|A_{J}|.}
Define the sets
B k = A I ∪ { k } for k ∈ N ∖ I . {\displaystyle B_{k}=A_{I\cup \{k\}}{\text{ for }}k\in N\smallsetminus I.}
We seek the number of elements in none of the Bk which, by the principle of inclusion–exclusion (with B ∅ = A I {\displaystyle B_{\emptyset }=A_{I}} ), is
∑ K ⊆ N ∖ I ( − 1 ) | K | | B K | . {\displaystyle \sum _{K\subseteq N\smallsetminus 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 BK = AJ, showing that the result is valid.
In probability In probability, for events A1, ..., An in a probability space ( Ω , F , P ) {\displaystyle (\Omega ,{\mathcal {F}},\mathbb {P} )} , the inclusion–exclusion principle becomes for n = 2
P ( A 1 ∪ A 2 ) = P ( A 1 ) + P ( A 2 ) − P ( A 1 ∩ A 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
P ( A 1 ∪ A 2 ∪ A 3 ) = P ( A 1 ) + P ( A 2 ) + P ( A 3 ) − P ( A 1 ∩ A 2 ) − P ( A 1 ∩ A 3 ) − P ( A 2 ∩ A 3 ) + P ( A 1 ∩ A 2 ∩ A 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
P ( ⋃ i = 1 n A i ) = ∑ i = 1 n P ( A i ) − ∑ i < j P ( A i ∩ A j ) + ∑ i < j < k P ( A i ∩ A j ∩ A k ) + ⋯ + ( − 1 ) n − 1 P ( ⋂ i = 1 n A i ) , {\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
P ( ⋃ i = 1 n A i ) = ∑ k = 1 n ( ( − 1 ) k − 1 ∑ I ⊆ { 1 , … , n } | I | = k P ( A I ) ) , {\displaystyle \mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)=\sum _{k=1}^{n}\left((-1)^{k-1}\sum _{I\subseteq \{1,\ldots ,n\} \atop |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
A I := ⋂ i ∈ I A i {\displaystyle A_{I}:=\bigcap _{i\in I}A_{i}}
denotes the intersection of all those Ai with index in I. According to the Bonferroni inequalities, the sum of the f