TAOCP 1.3.3 Exercise 26

Let $S_1, S_2, \ldots, S_M$ be subsets of a fixed universe $U$.

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.3.3: Applications to Permutations

Exercise 26. [M24] Extend the principle of inclusion and exclusion to obtain a formula for the number of elements that are in exactly $r$ of the subsets $S_1, S_2, \ldots, S_M$. (The text considers only the case $r = 0$.)

Verified: yes
Solve time: 26m57s

Solution

Let $S_1, S_2, \ldots, S_M$ be subsets of a fixed universe $U$. For each element $x \in U$, define

$$ t(x) = #{i : x \in S_i}. $$

The quantity required is

$$ N_r = #{x \in U : t(x) = r}. $$

For each integer $k$ with $0 \le k \le M$, define

$$ A_k = \sum_{1 \le i_1 < i_2 < \cdots < i_k \le M} \left| S_{i_1} \cap S_{i_2} \cap \cdots \cap S_{i_k} \right|. $$

Each element $x \in U$ contributes to $A_k$ once for each $k$-subset of the indices $i$ such that $x \in S_i$. Hence the contribution of $x$ to $A_k$ equals $\binom{t(x)}{k}$, so

$$ A_k = \sum_{x \in U} \binom{t(x)}{k}. $$

Consider the expression

$$ \sum_{k=r}^{M} (-1)^{k-r} \binom{k}{r} A_k. $$

Substitution of the expression for $A_k$ yields

$$ \sum_{k=r}^{M} (-1)^{k-r} \binom{k}{r} \sum_{x \in U} \binom{t(x)}{k} = \sum_{x \in U} \sum_{k=r}^{M} (-1)^{k-r} \binom{k}{r} \binom{t(x)}{k}. $$

For fixed $x$, the summand vanishes when $k > t(x)$, so the inner sum reduces to

$$ \sum_{k=r}^{t(x)} (-1)^{k-r} \binom{k}{r} \binom{t(x)}{k}. $$

Fix $t \ge 0$ and consider

$$ \sum_{k=r}^{t} (-1)^{k-r} \binom{k}{r} \binom{t}{k}. $$

The identity

$$ \binom{k}{r} \binom{t}{k} = \binom{t}{r} \binom{t-r}{k-r} $$

transforms the sum into

$$ \binom{t}{r} \sum_{k=r}^{t} (-1)^{k-r} \binom{t-r}{k-r}. $$

With the change of variable $j = k-r$, this becomes

$$ \binom{t}{r} \sum_{j=0}^{t-r} (-1)^j \binom{t-r}{j} = \binom{t}{r} (1-1)^{t-r}. $$

If $t > r$, then $(1-1)^{t-r} = 0$, hence the expression equals $0$. If $t = r$, then the sum reduces to $\binom{r}{r} = 1$. Therefore,

$$ \sum_{k=r}^{t} (-1)^{k-r} \binom{k}{r} \binom{t}{k} = \begin{cases} 1, & t=r,\ 0, & t \ne r. \end{cases} $$

Consequently, each element $x \in U$ contributes $1$ to the total sum if and only if $t(x)=r$, and contributes $0$ otherwise. Hence the whole sum equals $N_r$:

$$ N_r = \sum_{k=r}^{M} (-1)^{k-r} \binom{k}{r} A_k. $$

This completes the proof. ∎