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

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.
