Intuition for Inclusion-Exclusion Principle

Question

Many of us are familiar with the inclusion-exclusion principle. I think the principle makes total sense when applied to the two or three sets and we have the following:

$|A\cup B|=|A|+|B|-|A\cap B|$

$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A \cap B \cap C|\text{.}$

However, it is not as easy to understand how this works in the general case. In lieu of a rigorous proof, it is easy to see that the IEP rests on the following principle: suppose that $x$ is a member of $n$ sets. Then $x$ gets counted $n$ times on the first count, subtracted $n$ choose $2$ times on the second count, added back in $n$ choose $3$ times on the third count, etc. In other words:

$${n \choose 1}-{n\choose 2}+{n\choose 3}-{n\choose 4}+\cdots+(-1)^{n+1}{n \choose n}=1$$

Or, perhaps more appropriately written as

$${n\choose 0}-{n \choose 1}+{n\choose 2}+\cdots+(-1)^{n}{n \choose n}=0$$

I should clarify that the proof of this is easy to do algebraically, but I am looking for a useful intuitive explanation of the above property, and I'm curious how people view the IEP from a combinatorial perspective.

Answer 1

One essential aspect of the Inclusion-Exclusion Principle (IEP) is the transformation of at least information to exact information.

• If counting objects having at least a number of properties is simple, but counting objects having exactly a number of properties is difficult, than the IEP comes into play.

• The objects are represented by the elements contained in $A_1,\dots,A_n$ and the properties of an element $x$ are the sets $A_j,1\leq j\leq n$, which contain $x$.

If we have this essence of IEP in mind and we look at the expression:

\begin{align*} \left|\bigcup_{j=1}^{n}A_j\right|=\sum_{j=1}^{n}\left|A_j\right| -\sum_{1\leq i \leq j \leq n}\left|A_i\cap A_j\right|\pm\cdots+(-1)^{n-1}\left|\bigcap_{j=1}^{n}A_j\right| \end{align*}

we observe, that the right hand side (RHS) consists of summands with at least information.

Note, that the summand

$$\left|A_i\cap A_j\right|\quad \text{in}\quad\sum_{1\leq i \leq j \leq n}\left|A_i\cap A_j\right|$$

is not only the number of elements which are in $A_i$ and $A_j$ it is more precisely the number of elements which are at least in $A_i$ and $A_j$, since elements $x$ in $A_i\cap A_j$ may also be contained in other sets of $A_1,\dots,A_n$.

Whereas the LHS $$\left|\bigcup_{j=1}^{n}A_j\right|$$ presents the number of elements which are exactly in $\bigcup_{j=1}^{n}A_j$.

We observe the IEP transforms counting information with at least properties into counting information with exact properties.

Note: This intuitive connection between at least and exact information has a formal represention. Using generating functions you will get a kind of eye-birds view at hand, which transforms the at least to an exact information as simple shift by one of the argument. For more information about this approach you may have a look at section 4.2 of H.S. Wilfs Generatingfunctionology.

Answer 2

The way I usually think of the Inclusion-Exclusion Principle goes something like this:

If something is in $n$ of the $S_j$, it will be counted $\binom{n}{k}$ times in the sum of the sizes of intersections of $k$ of the $S_j$. Therefore, it will be counted $$ \sum_{k\ge1}(-1)^{k-1}\binom{n}{k}=1\tag{1} $$ time in the expression $$ \begin{align} &\overbrace{\sum_i\left|S_i\right|}^{\binom{n}{1}}-\overbrace{\sum_{i\lt j}\left|S_i\cap S_j\right|}^{\binom{n}{2}}+\overbrace{\sum_{i\lt j\lt k}\left|S_i\cap S_j\cap S_k\right|}^{\binom{n}{3}}-\dots\tag{2} \end{align} $$ where the expression above each sum is the number of times an object in $n$ of the $S_j$ will be counted in that sum.

Thus, because of $(1)$, any object, no matter how many of the $S_j$ it is in (no matter what $n$ is), will be counted only once in $(2)$.

Answer 3

In combinatorics, it's well-known that for a non-empty set, the number of non-empty odd subsets is equal to the number of non-empty even subsets plus one:

$$ \sum_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor}\binom{n}{2k-1}=1+ \sum_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor}\binom{n}{2k} $$

Inclusion and Exclusion

Let's define an even intersection as an intersection of an even number of sets. An odd intersection is an intersection of an odd number of sets.

Let John sum the number of elements in all possible odd intersections while Mary sum the number of elements in all even intersections. John will count each unique element exactly once more than Mary. Therefore, by subtracting Mary's number from John's number, we get the number of unique elements.