Tag Archives: enumeration

The Inclusion Exclusion Principle

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 |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C| where A,B,C are three finite sets.

Here we start off by summing the number of elements inĀ A,B,C seperately. The overcount is compensated by subtracting the number of elements in |A\cap B|,|A\cap C|, |B\cap C|. We actually compensate for a bit more then needed and so to arrive at the correct count we must add |A\cap B\cap C|.

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 X is any set containing n elements and k is any field, then the set of all functions f:X\to k is an n-dimensional vector space V over k with the naturally induced operations.

Proof: Let X=\{x_1,\cdots,x_n\}. It is easy to see that V together with the operations f+g, defined by (f+g)(x_i)=f(x_i)+g(x_i) and (\alpha f)(x_i)=\alpha (f(x_i)) for all x_i\in X is a vector space.

We now exhibit a basis for V consisting of n elements. For all x_i\in X let f_{x_i} be the function defined as f_{x_i}(y)=\begin{cases}         \hfill 1    \hfill & \text{ if }y=x_i \\        \hfill 0 \hfill & \text{ otherwise} \\    \end{cases}. Now, we claim that B=\{f_{x_i}:x_i\in X\} is a basis. Clearly it is spanning as for any f\in V we have f=\sum_{x_i\in X}f(x_i)f_{x_i}. It is linearly independent as \sum_{x_i\in X} \alpha_i f_{x_i}=0 means that for any j, with 1\le j\le n, we have \sum_{x_i\in X} \alpha_i f_{x_i}(x_j)=0, i.e. \alpha_j=0. This completes the proof.\Box

Lemma 2: If m\ge 0 then \sum_{i \mathop = 0}^m \left({-1}\right)^i \binom m i = \delta_{0m}.

Proof: If m>0 put x=1, y=-1 in the binomial theorem (x+y)^m=\sum_{i=0}^mx^{m-i}y^i. If m=0, then the sum on the left reduces to only one term: (-1)^0\binom 0 0. This is clearly 1.\Box

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 S be a set with n elements. Let V be the 2^n dimensional vector space of all functions f:\mathcal{P}(S)\to k, where k is some field and \mathcal{P}(S) is the power set of S. Let \phi:V\to V be the linear operator defined by

\displaystyle\phi f(T)=\sum_{Y\supseteq T}f(Y)\text{ for all } T\subseteq S.

Then \phi^{-1} exists and is given by:

\displaystyle\phi^{-1} f(T)=\sum_{Y\supseteq T}(-1)^{|Y-T|}f(Y)\text{ for all } T\subseteq S.

Proof: To show \phi^{-1} as given above is indeed the inverse it suffices to show that \phi^{-1}\phi(f)=f for all f\in V.

Let f\in V. Then,

\displaystyle\phi^{-1}\phi f(T)=\sum_{Y\supseteq T}(-1)^{|Y-T|}\phi f(Y)=\sum_{Y\supseteq T}(-1)^{|Y-T|}\sum_{Z\supseteq Y}f(Z)=\sum_{Z\supseteq T}\Big(\sum_{Z\supseteq Y\supseteq T}(-1)^{|Y-T|}\Big)f(Z)

Now fix Z,T and let m=|Z-T|. Consider \displaystyle\sum_{Z\supseteq Y\supseteq T}(-1)^{|Y-T|}. Any Y is obtained by choosing some elements out of Z-T which has m elements, and taking the union of such elements with T. So for every i, with 0\le i\le m, there are exactly \binom m i ways of choosing a Y, which has i+|T| elements. Any such Y also has i elements in |Y-T|. So \displaystyle\sum_{Z\supseteq Y\supseteq T}(-1)^{|Y-T|}=\sum_{i=0}^m(-1)^i\binom m i=\delta_{0m}. This when substituted in the expression for \phi^{-1}\phi f(T) shows that \phi^{-1}\phi f(T)=f(T), which proves the theorem.\Box

We now discuss some corollaries of the Inclusion Exclusion principle. Let S be a set of properties that elements of a given set A may or may not have. For any T\subseteq S, let A'_T\subseteq A be those elements which have exactly the properties in T and no others. We define a function f_=:S\to \mathbb{R} such that f_=(T)=|A'_T|. Similarly, for any T\subseteq S, let A''_T\subseteq A be those elements which have at least the properties in T. We define a function f_\ge:S\to \mathbb{R} such that f_=(T)=|A''_T|. It is clear that \displaystyle f_\ge(T)=\sum_{Y\supseteq T}f_=(T) for any T\subseteq S, and so by the Inclusion Exclusion principle we conclude that

Corollary 4: For any T\subseteq S, we have \displaystyle f_=(T)=\sum_{Y\supseteq T}(-1)^{|Y-T|}f_\ge (Y).

In particular we have \displaystyle f_=(\emptyset)=\sum_{Y\subseteq S}(-1)^{|Y|}f_\ge (Y), which gives us a formula for the number of elements having none of the properties.\Box

In the above corollary we think of f_\ge(T) as the first approximation to f_=(T). So we “include” that much “quantity” in our initial count. From this we subtract all terms of the type f_=(Y) where Y has just one extra element then T. Thus we “exclude” that much “quantity” from our count. This gives a better approximation. Next we add all terms of the type f_=(Y) where Y has two extra elements then T, and so on. This is the reason behind the terminology inclusion-exclusion.

We now discuss another corollary. Let A be a finite set and let A_1,\cdots A_n be some of its subsets. We define a set of properties S=\{P_1,\cdots,P_n\} which elements of A may or may not enjoy as follows: For any i, with 1\le i\le n, x\in A satisfies the property P_i if and only if x\in A_i. Also for any I\subseteq [n], let \emptyset\ne A_I=\cap_{i\in I}A_i be the set of elements which have at least the properties P_i for i\in I. Define A_\emptyset to be A. By Corollary 4, \displaystyle f_=(\emptyset)=\sum_{I'\subseteq S}(-1)^{|I'|}f_\ge (I')=\sum_{I\subseteq [n]}(-1)^{|I|}|A_I| where in the second equality we correspond each subset of properties with a subset of [n]. We summarize this as

Corollary 5: Let A be a finite set and let A_1,\cdots A_n be some of its subsets. For any \emptyset\ne I\subseteq [n], let A_I=\cap_{i\in I}A_i and let A_\emptyset=A. The number of elements in A-\cup_{i=1}^n A_i is given by \displaystyle\sum_{I\subseteq [n]}(-1)^{|I|}|A_I|=|A|+\sum_{\emptyset\ne I\subseteq [n]}(-1)^{|I|}|A_I|.\Box

A further special case is obtained by considering any finite sets A_1,A_2,\cdots,A_n and letting A=\cup_{i=1}^nA_i. Then the above corollary translates to \sum_{I\subseteq [n]}(-1)^{|I|}|A_I|=0. Considering the case of I=\emptyset seperately, we see that |A|+\displaystyle\sum_{\emptyset\ne I\subseteq [n]}(-1)^{|I|}|\cap_{i\in I}A_i|=0. This easily yields the following corollary.

Corollary 6: Let A_1,A_2\cdots,A_n be any finite sets. For any \emptyset\ne I\subseteq [n], let A_I=\cap_{i\in I}A_i and let A_\emptyset=A. Then \displaystyle|A_1\cup A_2\cup\cdots\cup A_n|=\displaystyle\sum_{\emptyset\ne I\subseteq [n]}(-1)^{|I|-1}|\cap_{i\in I}A_i|.\Box

Now by grouping terms involving the same size of I we can restate both Corollary 5 and 6 as follows.

Corollary 7: Let A be a finite set and let A_1,\cdots A_n be some of its subsets. The number of elements in A-\cup_{i=1}^n A_i is given by
\displaystyle |A|+\sum_{k=1}^n(-1)^{k}\sum_{1\le i_1 < i_2 < \cdots <i_k\le n}|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_k}|.\Box

Corollary 8: If A_1,A_2\cdots,A_n are any finite sets then

\displaystyle|A_1\cup A_2\cup\cdots\cup A_n|=\sum_{k=1}^n(-1)^{k-1}\sum_{1\le i_1< i_2<\cdots<i_k\le n}|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_k}|.\Box

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 k distinct sets A_i always has the same cardinality N_k. In that case we only need to multiply N_k with the number of such ways to select the k sets to get the value of the inner sums in Corollaries 7 and 8.

Corollary 9: Let A be a finite set and let A_1,\cdots A_n be some of its subsets. Suppose that for any k with 1\le k\le n there exists a natural number N_k so that for any \{i_1,\cdots, i_k\}\subseteq [n] we have A_{i_1}\cap\cdots\cap A_{i_k}=N_k. Then the number of elements in A-\cup_{i=1}^n A_i is given by |A|+\sum_{k=1}^n(-1)^k\binom{n}{k}N_k and |A_1\cup A_2\cup\cdots\cup A_n|=\sum_{k=1}^n(-1)^{k-1}\binom{n}{k}N_k.\Box

Leave a comment

Filed under Combinatorics, Set theory