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$
    – Thomas Andrews
    Commented 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$
    – user2661923
    Commented Nov 21, 2021 at 19:02

1 Answer 1

Reset to default
1
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .