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$?
 A: As Chris Eagle says in the comments, this can be taken as the definition of ${n\choose k}$. However, what I think you are asking is how can we prove that the number of ways of choosing $k$ elements from $n$ is $\frac{n!}{(n-k)!k!}$?
Maybe you will accept this proof:
You are choosing $k$ elements from a set of $n$, and ordering doesn't matter. There are $n$ ways to choose the first element, $n-1$ ways to choose the second, $n-2$ ways to choose the third et cetera, and $(n+1-k)$ ways to choose the $k$th. Therefore there are
$$n(n-1)(n-2)\cdots(n+1-k)$$
ways to choose the $k$ elements, which we can also write as
$$\frac{n!}{(n-k)!}$$
using the definition of the factorial function. But this over counts the number of possible subsets - any subset of the same elements is identical. Since the subset contains distinct elements, any re-ordering of the order we chose them in gives the same subset. Following a similar logic to that used previously, there are $k$ ways to choose the first element of a re-ordering, $k-1$ ways to choose the second et cetera, for a total of
$$k(k-1)\cdots 2\cdot 1 = k!$$
different reorderings, so we divide by this number, giving a total of
$$\frac{n!}{(n-k)!k!} \equiv {n\choose k}$$
ways to choose a subset of $k$ elements from a set of $n$ elements.
A: 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. 
A: Do you agree that the set $S$ is in bijection with all subsets of $A$ with $k$ elements?  Srivatsan Narayanan's comment should clear this up.  Please ask for clarification if it does not.
Every subset of $A$ with $k$ elements can be realized as the first $k$ elements of some ordering of $A$.  Say two orderings are "equivalent" if they give rise to the same subset of $A$ with $k$ elements.  There are $n!$ orderings of $A$, but there are $k!$ equivalent ways to order the first $k$ elements, and $(n-k)!$ equivalent ways to order the final $n-k$ elements.  Thus, there are
\begin{equation*}
\frac{n!}{k!(n-k)!} = {n \choose k}
\end{equation*}
equivalent orderings of $A$.  In particular there are ${n \choose k}$ distinct subsets of $A$ with $k$ elements.
