Counting Number of  k-tuples Let $A = \{a_1, \dots, a_n\}$ be a collection of distinct elements and let $S$ denote the collection all $k$-tuples $(a_{i_1}, \dots a_{i_k})$ where $i_1, \dots i_k$ is an increasing sequence of numbers from the set $\{1, \dots n \}$. How can one prove rigorously, and from first principles, that the number of elements in $S$ is given by $n \choose k$?

We will show that the number of ways of selecting a subset of $k$ distinct objects from a pool of $n$ of them is given by the binomial coefficient 
$$
\binom{n}{k} = \frac{n!}{k!(n-k)!}.
$$
I find this proof easiest to visualize. First imagine permuting all the $n$ objects in a sequence; this can be done in $n!$ ways. Given a permutation, we pick the first $k$ objects, and we are done. 
But wait! We overcounted... 


*

*Since we are only interested in the subset of $k$ items, the ordering of the first $k$ items in the permutation does not matter. Remember that these can be arranged in $k!$ ways. 

*Similarly, the remaining $n-k$ items that we chose to discard are also ordered in the original permutation. Again, these $n-k$ items can be arranged in $(n-k)!$ ways. 


So to handle the overcounting, we simply divide our original answer by these two factors, resulting in the binomial coefficient. 

But honestly, I find this argument slightly dubious, at least the way I wrote it. Are we to take on faith that we have taken care of all overcounting? And, why exactly are we dividing by the product of $k!$ and $(n-k)!$ (and not some other function of these two numbers)? 
One can make the above argument a bit more rigorous in the following way. Denote by $S_n$, $S_k$ and $S_{n-k}$ be the set of permutations of $n$, $k$ and $n-k$ objects respectively. Also let $\mathcal C(n,k)$ be the $k$-subsets of a set of $n$ items. Then the above argument is essentially telling us that 

There is a bijection between $S_n$ and $\mathcal C(n,k) \times S_k \times S_{n-k}$. 

Here $\times$ represents Cartesian product. The formal description of the bijection is similar to the above argument: specify the subset formed by the first $k$ items, specify the arrangement among the first $k$ items, specify the arrangement among the remaining $n-k$ items. (The details are clear, I hope. :)) 
Given this bijection, we can then write:
$$
|S_n| = |\mathcal C(n,k)| \cdot |S_k| \cdot |S_{n-k}|,
$$
which is exactly what we got before. 
