The Inclusion Exclusion Principle is one of most fundamental results in combinatorics. It deals with counting through a seive technique: i.e. we first overcount the quantity to be enumerated, then we try to balance out the overcounting by subtracting the extra. We may or may not subtract more then what is needed and so we count again the extra bits. Continuing in this way we “converge” at the correct count.
An easy example is where are three finite sets.
Here we start off by summing the number of elements in seperately. The overcount is compensated by subtracting the number of elements in ,, . We actually compensate for a bit more then needed and so to arrive at the correct count we must add .
Our goal here is to prove the inclusion-exclusion principle and then to look at a few corollaries. We first establish two lemmas.
Lemma 1: If is any set containing elements and is any field, then the set of all functions is an -dimensional vector space over with the naturally induced operations.
Proof: Let . It is easy to see that together with the operations , defined by and for all is a vector space.
We now exhibit a basis for consisting of elements. For all let be the function defined as . Now, we claim that is a basis. Clearly it is spanning as for any we have . It is linearly independent as means that for any , with , we have , i.e. . This completes the proof.
Lemma 2: If then .
Proof: If put in the binomial theorem . If , then the sum on the left reduces to only one term: . This is clearly .
We now prove the Inclusion Exclusion principle. This theorem in its purest form, is simply a formula for an inverse of a linear operator. The theorem is as follows:
Theorem 3: Let be a set with elements. Let be the dimensional vector space of all functions , where is some field and is the power set of . Let be the linear operator defined by
Then exists and is given by:
Proof: To show as given above is indeed the inverse it suffices to show that for all .
Let . Then,
Now fix and let . Consider . Any is obtained by choosing some elements out of which has elements, and taking the union of such elements with . So for every , with , there are exactly ways of choosing a , which has elements. Any such also has elements in . So . This when substituted in the expression for shows that , which proves the theorem.
We now discuss some corollaries of the Inclusion Exclusion principle. Let be a set of properties that elements of a given set may or may not have. For any , let be those elements which have exactly the properties in and no others. We define a function such that . Similarly, for any , let be those elements which have at least the properties in . We define a function such that . It is clear that for any , and so by the Inclusion Exclusion principle we conclude that
Corollary 4: For any , we have .
In particular we have , which gives us a formula for the number of elements having none of the properties.
In the above corollary we think of as the first approximation to . So we “include” that much “quantity” in our initial count. From this we subtract all terms of the type where has just one extra element then . Thus we “exclude” that much “quantity” from our count. This gives a better approximation. Next we add all terms of the type where has two extra elements then , and so on. This is the reason behind the terminology inclusion-exclusion.
We now discuss another corollary. Let be a finite set and let be some of its subsets. We define a set of properties which elements of may or may not enjoy as follows: For any , with , satisfies the property if and only if . Also for any , let be the set of elements which have at least the properties for . Define to be . By Corollary 4, where in the second equality we correspond each subset of properties with a subset of . We summarize this as
Corollary 5: Let be a finite set and let be some of its subsets. For any , let and let . The number of elements in is given by .
A further special case is obtained by considering any finite sets and letting . Then the above corollary translates to . Considering the case of seperately, we see that . This easily yields the following corollary.
Corollary 6: Let be any finite sets. For any , let and let . Then .
Now by grouping terms involving the same size of we can restate both Corollary 5 and 6 as follows.
Corollary 7: Let be a finite set and let be some of its subsets. The number of elements in is given by
Corollary 8: If are any finite sets then
Corollaries 5 to 8 are often referred to as the principle of inclusion-exclusion themselves as in combinatorial settings they are the ones most often used. A further simplified version can also be derived from them when the intersection of any distinct sets always has the same cardinality . In that case we only need to multiply with the number of such ways to select the sets to get the value of the inner sums in Corollaries 7 and 8.
Corollary 9: Let be a finite set and let be some of its subsets. Suppose that for any with there exists a natural number so that for any we have . Then the number of elements in is given by and .