# inclusion exclusion proof

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

• $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? Nov 21, 2021 at 17:57
• 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}.$$ Nov 21, 2021 at 19:02

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