Today I was reading about the inclusion/exclusion principle. And I saw some part of a formula that looks like this: $\sum\limits_{i<j<k} (|A_i\bigcap A_j\bigcap A_k|)$
In order to apply it, we have to look at all the triples $\langle i,j,k\rangle$, such that $1\leq i,j,k\leq n$ and $i<j<k$.
But my question is: how many such triples are there? How many such quadruples are there? Quintuples? $N$-tuples ($n$ and $N$ are different)? Is there a formula?
On
There are ${n \choose 3}$ such triples, ${n \choose 4}$ quadruples etc. Generally, for $N$ there are ${n \choose N}$ $N$-tuples. Indeed, observe that set of $N$-tuples $(a_1, \cdots, a_N)$ such that $1\leq a_1<\cdots a_n\leq N$ is in bijection with set of all subsets of set $\{1,\cdots,n\}$, which have $N$ elements. It's easy to show this bijection and I leave it for you.
I guess there is an equivalence between any set of $N$ different numbers in $\{1,2,\dots,n\}$ and the $N$-tuples, because, once we get the numbers, the order is fixed: $i_1<i_2<\dots <i_N$. So it would be $C_n^N$. What do you think?