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

-
This is the definition of $n \choose k$. – Chris Eagle Oct 4 '11 at 22:16
I think the restriction that the sequence is "increasing" is confusing for you. Imagine picking any $k$-subset of items from a collection of $n$ items. This can be done in $\binom n k$ ways. Having chosen this, you do not have much choice: just sort them and that is the sequence. That is, after choosing the subset of indices, the number of ways you can form an increasing sequence out of them is just 1. Now putting together these two facts, the answer is $\binom n k$. – Srivatsan Oct 4 '11 at 22:20
@Chris So, you're saying that it is axiomatic that the number of elements in $S$ as described above is given by $n \choose k$ = $\frac{n!}{k!(n - k)!}$ ? I don't see how it's immediate or obvious that this number is equal to the number of elements in $S$ – ItsNotObvious Oct 4 '11 at 22:21
@Srivatsan I'm not confused about the term "increasing". Given a finite number of elements, I can easily enumerate all of the increasing tuples and then count them. What I don't understand is how to turn this into a rigorous argument from first principles. – ItsNotObvious Oct 4 '11 at 22:25
@3Sphere Yes, now I think I understand what your question really is. :) – Srivatsan Oct 4 '11 at 22:29

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.

-
Thanks; that helps a lot. I understand how you arrive at the first expression and how this over-counts the number of elements because it doesn't take duplicates into account. I'm not sure though I understand exactly how you are defining the "re-ordering" set; is this just the number of sequences of length $k$? – ItsNotObvious Oct 4 '11 at 22:40
Yes, that's right. – Chris Taylor Oct 5 '11 at 8:02

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.

-
How does one write down the bijection between $S_n$ and $C(n,k) \times S_k \times S_{n-k}$? Is this a theorem that I can look up somewhere? – ItsNotObvious Oct 5 '11 at 1:58
Well, isn't it exactly what I described. To specify a permutation, you need to specify the first $k$ terms (as a subset, so no order implied), then you need to specify the permutation among those $k$ terms, and finally, you need to specify the permutation among the remaining $n-k$ terms. Do you want to know how to specify it more formally? (You should check that this correspondence works in both directions.) – Srivatsan Oct 5 '11 at 2:01

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.

-