# principle of inclusion exclusion.

$e_i$ => number of objects satisfying exactly i properties.

$s_i$ => number of objects satisfying atleast i properties.

$s_0 = n$

$s_1= \sum_{i=1}^n N(a_i)$

$s_2= \sum_{i=1,j=2,i<j}^n N(a_i,a_j)$

$e_0$ = $s_0 - s_1 +s_2+......+(-1)^rs_r$

I did not understand how the expression for $e_i$ is proved.

$e_m$ = $s_m - {m + 1 \choose 1}s_{m+1} + {m+2\choose 2} s_{m+2}+...+(-1)^r {r \choose r-m}s_r$.

• Prove it one object at a time, since every $e_i$ and $s_i$ is just the sum, over all the objects, of appropriate 1s and 0s. – Greg Martin Mar 17 '13 at 7:41

You have $r$ properties, denoted by $a_1,a_2,\dots,a_r$. For any set $S\subseteq\{a_1,\dots,a_r\}$ of properties, $N(S)$ is the number of objects having all of the properties in $S$. For example, $N\big(\{a_1\}\big)$ is the number of objects with property $a_1$, and $N\big(\{a_1,a_3\}\big)$ is the number with both property $a_1$ and property $a_2$. (This notation is slightly different from the notation in the question, but it makes things a little easier.) For $i=0,\dots,r$, $e_i$ is the number of objects with exactly $i$ of the $r$ properties, and $s_i$ is the number with at least $i$ of the properties. The total number of objects is $n$; clearly every object has at least $0$ of the properties, so $s_0=n$.

It’s easy to express the numbers $s_i$ in terms of the numbers $N(a_k)$:

$$s_i=\sum\left\{N(S):S\subseteq\{a_1,\dots,a_r\}\text{ and }|S|=i\right\}\;.$$

E.g., for $i=1$ this is just $$\sum_{k=1}^rN\big(\{a_k\}\big)\;.$$

We want to prove that for $m=0,\dots,r$,

\begin{align*} e_k&=s_k-\binom{k+1}1s_{k+1}+\ldots+(-1)^r\binom{r}{r-m}s_r\\ &=\sum_{m=k}^r(-1)^{m-k}\binom{m}{m-k}s_m\\ &=\sum_{m=k}^r(-1)^{m-k}\binom{m}ks_m\;. \end{align*}

There are several ways to do this, so the one that I’m going to use may not be the one that you’ve already seen.

Suppose that $x$ is an object with at least $m$ of the $r$ properties. Then there is a $k$ such that $m\le k\le r$ and $x$ has exactly $k$ of the properties. Let $P$ be the set of $k$ properties possessed by $x$; $P$ has $\binom{k}m$ subsets of size $m$, and $x$ is counted once for each of them in the calculation of $e_m$, so $x$ contributes a total of $\binom{k}m$ to $e_m$. It follows that the $e_k$ objects with $k$ of the properties contribute a total of $\binom{k}me_k$ to $e_m$ and hence that $$s_m=\sum_{k=m}^r\binom{k}me_k\;.\tag{1}$$

Now I’ll define two polynomials: let

$$S(x)=\sum_{k=0}^rs_kx^k\quad\text{and}\quad E(x)=\sum_{k=0}^re_kx^k\;.$$

In view of $(1)$ we have

\begin{align*} S(x)&=\sum_{m=0}^rs_mx^m\\ &=\sum_{m=0}^r\sum_{k=m}^r\binom{k}me_kx^m\\ &=\sum_{k=0}^r\sum_{m=0}^k\binom{k}me_kx^m&&\text{reverse the order of summation}\\ &=\sum_{k=0}^re_k\sum_{m=0}^k\binom{k}mx^m\\ &=\sum_{k=0}^re_k(x+1)^k&&\text{by the binomial theorem}\\ &=E(x+1)\;. \end{align*}

Of course this implies that $E(x)=S(x-1)$, and we can reverse the above calculation to find that

\begin{align*} E(x)&=S(x-1)\\ &=\sum_{m=0}^rs_m(x-1)^m\\ &=\sum_{m=0}^rs_m\sum_{k=0}^m(-1)^{m-k}\binom{m}kx^k&&\text{binomial theorem again}\\ &=\sum_{k=0}^r\sum_{m=k}^r(-1)^{m-k}\binom{m}ks_mx^k&&\text{reverse the order again}\;. \end{align*}

The coefficient of $x^k$ in $E(x)$ is therefore

$$e_k=\sum_{m=k}^r(-1)^{m-k}\binom{m}ks_m\;,$$

exactly as we wanted.