12
$\begingroup$

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+B+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.

$\endgroup$
  • 1
    $\begingroup$ have you seen a bijective proof for exclusion inclusion, you can find it in Stnaley's enumerative combinatorics 1 $\endgroup$ – clark Oct 18 '15 at 21:41
6
+50
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ Do you mean for your sum to stop at $n$? $\endgroup$ – Ian Oct 18 '15 at 22:11
  • $\begingroup$ It will since, for $k\gt n$, all of the binomial coefficients are $0$. I have edited the sum to make it less confusing. $\endgroup$ – robjohn Oct 18 '15 at 22:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.