Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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