Intuition for Inclusion-Exclusion Principle 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.
 A: 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)$.
A: 
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.
