0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Greg Martin Mar 17 '13 at 7:41
1
$\begingroup$

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.

$\endgroup$

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.