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$?
Counting Number of k-tuples
-
0@3Sphere Yes, now I think I understand what your question really is. :) – 2011-10-04
3 Answers
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.
-
0Yes, that's right. – 2011-10-05
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.
-
0Well, 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.) – 2011-10-05
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.