# 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 .$\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.$\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$