Inclusion, exclusion principle

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 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 \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:

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 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:

Condensed: the full section is in Wikipedia.

In its general formula, the principle of inclusion, exclusion states that for finite sets A₁, ..., A_n, one has the identity

This can be compactly written as \[\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 \[\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,\) 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 S be a finite universal set containing all of the A_i and letting \(\overline{A_i}\) denote the complement of A_i in S, by De Morgan's laws we have \[\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 P₁, ..., P_n 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 A_i be the subset of elements of S which have the property P_i 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.

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 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 card correct. Then the number of orders, W, with at least one card being in the correct position, m, 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 \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} \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 \(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 \choose p}\) equal terms in the p summation (see combination).

\[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 \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: \[\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}\]

Condensed: the full section is in Wikipedia.

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 α_k = |A_J|, for every k-element subset J of {1, ..., n}, then \[\left |\bigcup_{i=1}^n A_i\right| =\sum_{k=1}^n (-1)^{k-1}\binom nk \alpha_k.\]

Or, in the complementary form, where the universal set S has cardinality α₀, \[\begin{aligned}\left |S \smallsetminus \bigcup_{i=1}^n A_i\right| &=\alpha_0 - \sum_{k=1}^n (-1)^{k-1}\binom nk \alpha_k \\&=\sum_{k=0}^n(-1)^k\binom nk \alpha_k.\end{aligned}\]

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 \(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 A_i is: \[\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: \[\sum_{J \supseteq I} (-1)^{|J| - |I|} |A_J|.\]

Define the sets \[B_k = A_{I \cup \{ k \}} \text{ for } k \in N \smallsetminus I.\]

We seek the number of elements in none of the B_k which, by the principle of inclusion, exclusion (with \(B_\emptyset = A_I\)), is \[\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 B_K = A_J, showing that the result is valid.

In probability, for events A₁, ..., A_n in a probability space \((\Omega,\mathcal{F},\mathbb{P})\), the inclusion, exclusion principle becomes for n = 2 \[\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 \[\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_{in which contain exactly k elements, and \[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 \(\mathbb{P}\) is replaced by the measure μ.

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 \[a_k=\mathbb{P}(A_I) \text{ for every } I\subset\{1,\ldots,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}\binom n k a_k\] due to the combinatorial interpretation of the binomial coefficient \(\binom nk\). For example, if the events \(A_i\) are independent and identically distributed, then \(\mathbb{P}(A_i) = p\) for all i, 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, \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{aligned} \mathbb{P}(P = A) &= \mathbb{P}(P \supset A) - \sum_{j_1 \in S \setminus A} \mathbb{P}(P \supset A \cup {j_1}) \\ &\hphantom{=} + \sum_{j_1, j_2 \in S \setminus A \atop j_1 \ne j_2} \mathbb{P}(P \supset A \cup {j_1, j_2}) + \dots \\ &\hphantom{=} + (-1)^{|S|-|A|} \mathbb{P}(P \supset S) \\ &= \sum_{A \subset J \subset S} (-1)^{|J|-|A|} \mathbb{P}(P \supset J). \end{aligned}\]

The principle is sometimes stated in the form that says that if \[g(A)=\sum_{S \subseteq A}f(S)\] then

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

Take \(\underline{m} = \{1,2,\ldots,m\}\), \(f(\underline{m}) = 0\), and \[f(S)=\left|\bigcap_{i \in \underline{m} \smallsetminus S} A_i \smallsetminus \bigcup_{i \in S} A_i\right| \text{ and } f(S) = \mathbb{P} \left(\bigcap_{i \in \underline{m} \smallsetminus S} A_i \smallsetminus \bigcup_{i \in S} A_i\right)\] respectively for all sets \(S\) with \(S \subsetneq \underline{m}\). Then we obtain \[g(A)=\left|\bigcap_{i \in \underline{m} \smallsetminus A} A_i\right|, \quad g(\underline{m}) = \left|\bigcup_{i \in \underline{m}} A_i \right| \text{ and } g(A) = \mathbb{P} \left( \bigcap_{i \in \underline{m} \smallsetminus A} A_i \right),~~ g(\underline{m}) = \mathbb{P} \left(\bigcup_{i \in \underline{m}} A_i\right)\] respectively for all sets \(A\) with \(A \subsetneq \underline{m}\). This is because elements \(a\) of \(\bigcap_{i \in \underline{m} \smallsetminus A} A_i\) can be contained in other \(A_i\) (\(A_i\) with \(i \in A\)) as well, and the \(\bigcap \smallsetminus \bigcup\)-formula runs exactly through all possible extensions of the sets \(\{A_i \mid i \in \underline{m} \smallsetminus A\}\) with other \(A_i\), counting \(a\) only for the set that matches the membership behavior of \(a\), if \(S\) runs through all subsets of \(A\) (as in the definition of \(g(A)\)).

Since \(f(\underline{m}) = 0\), we obtain from (2) with \(A = \underline{m}\) that \[\sum_{\underline{m} \supseteq T \supsetneq \varnothing}(-1)^{|T|-1} g(\underline{m} \smallsetminus T) = \sum_{\varnothing \subseteq S \subsetneq \underline{m}}(-1)^{m-|S|-1} g(S) = g(\underline{m})\] and by interchanging sides, the combinatorial and the probabilistic version of the inclusion, exclusion principle follow.

If one sees a number \(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 \(A - S\) is the multiset for which \((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 \(\mu(A - S)\) is just the \((-1)^{|A|-|S|}\) of (2) in case \(A - S\) is a set.

Condensed: the full section is in Wikipedia.

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.

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 A_k with respect to some universal set A such that \(A_k \subseteq A\) for each k. Then we have \[\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.

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.

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: \[\sum_{j=0}^{n} \binom{n}{j} (-1)^j (n-j)^k.\]

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: \[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.

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: \[S(n,k) = \frac{1}{k!}\sum_{t=0}^k (-1)^t \binom k t (k-t)^n.\]