How many terms are there in each of these sums?

Question

It is written on Wikipedia that we have:

$\mathbb P (\displaystyle \bigcup_{i=1}^{n}A_i)=\displaystyle \sum_{i=1}^{n} \mathbb P (A_i) - \displaystyle \sum_{i<j} \mathbb P(A_i \cap A_j) + \displaystyle \sum_{i<j<k} \mathbb P(A_i \cap A_j \cap A_k) - ... + (-1)^{n-1} \mathbb P (\bigcap_{i=1}^{n} A_i) $

Now, I would like to know how many terms are there in each of the sums in this formula so to better understand this formula itself.

For example, in sum $\displaystyle \sum_{i=1}^{n} \mathbb P (A_i)$ there are $n$ terms, in sum $\displaystyle \sum_{i<j} \mathbb P(A_i \cap A_j)$ there are $\frac{(n-1)n}{2}$ terms, because for $j=2$ we have $i=1$, for $j=3$ we have $j=1,2$, for...for $j=n$ we have $i=1,2,...(n-1)$.

I know that this is easy problem for some of you, so would be nice to see how would you derive how many terms there are in each sum?

Thanks.

Answer 1

It would be the binomial coefficient :

How many ways are there of choosing a set of $k$ elements amongst $n$ ?

Well ${n\choose k} = \frac{n!}{k! (n-k)!}$

About intuition, why is that formula the one your looking for ? suppose you have a list of values from $1$ to $n$ : $$[1,2,\dots,n]$$

How many ways are there to shuffle it ? $n!$ since you have $n$ ways of placing $1$, then $n-1$ ways of placing $2$ amongst the remaining places, etc until you place $n$ in the last possible spot.

Now suppose you select from this shuffled list only the $k$ first elements but you don't care about the ordering of the elements (since anyway you will sum only once because you have $i<j<k<...$). So you want to remove the order of the first $k$ elements but also the order of the $n-k$ last elements, all you care about is the elements that are actually the first $k$. We already know that there are $k!$ ways of ordering the first $k$ elements and $(n-k)!$ ways of ordering the $(n-k)$ last, so you need to "remove" that from the different ordering by dividing. And so you obtain ${n\choose k} = \frac{n!}{k! (n-k)!}$

A cool fact about that is that the binomial theorem tells you that total amount of terms in the end is

$$\sum_{k=0}^n {n\choose k} = \sum_{k=0}^n {n\choose k} 1^k 1^{n-k} = 2^n$$

which can be checked quite easily.

Answer 2

Once you note that the number is equal to the number of the ways of choosing $k$ elements from the $n$ elements in total, which is denoted by ${n \choose k}$ or $C_n^k$, you can calculate $C_n^k$ just by generalizing your method.
First multiplying from $n$ to $n-k+1$, that is to say, the first element has $n$ options, the second has $n-1$, and so on.
However, there are many ways to choose the elements getting the same consequence finally, since the selected elements are actually the same although they were chosen in different order. And the number of $k$ elements in different order is $k!=k(k-1)...1$ which can be worked out analogously.
Then the number you need is $$\frac{n(n-1)...(n-k+1)}{k(k-1)...1}$$. This is a formula: $C_n^k=\frac{n!}{k!(n-k)!}$