0
$\begingroup$

there is a step in this proof for the Principle of inclusion-exclusion that is not so clear to me:

\begin{multline*} |A_1 \cup A_2 \cup \cdots \cup A_n| = \sum_{1 \leq i \leq n} |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| \\ + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1} |A_1 \cap A_2 \cap \cdots \cap A_n|. \end{multline*}

Supposing that $a$ belongs to $r$ original sets, then it is counted $r$ times by the first expression, so it is counted $C(r,1)$ times.

Then my book explains that $a$ is counted $C(r,2)$ times by the second expression, $C(r,3)$ by the third expression and so on up.

Why do we count $a$ $C(r,2)$ times in the second expression?

Thanks for the help

$\endgroup$
2
  • 1
    $\begingroup$ $a\in A_i\cap A_j$ iff $a\in A_i,$ and $a\in A_j.$ How many ways are there to pick $i,j$ if there are $r$ of them? $\endgroup$ Nov 21, 2021 at 17:57
  • $\begingroup$ As a way of expanding your intuition, try a manual example where $n = 5$, and $A_1 = \{1,2,3,4,5\}$, and $A_2 = \{1,2,3,4\}$, and $A_3 = \{1,2,3\}$ and $A_4 = \{1,2\}$ and $A_5 = \{1\}$. First, manually apply the formula that you were taught for enumerating $|A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_5|$. Then, take each of the elements $(1), (2), (3), (4), (5)$, and enumerate exactly how many ways that each of the elements is counted, because of the formula. Also, note that (per binomial expansion), $$\forall ~s ~\in ~\Bbb{Z^+}, ~~~0 = ([-1] + 1)^s = \sum_{k=0}^s (-1)^k\binom{s}{k}.$$ $\endgroup$ Nov 21, 2021 at 19:02

1 Answer 1

0
$\begingroup$

In the second sum, for each $a$ there is one term for each pair of sets both of which contain $a$. There are $C(r,2)$ ways to choose such pairs.

I suggest you draw a Venn diagram and look at all the relevant subsets when $n=3$.

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