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

  • $\begingroup$ This is the definition of $n \choose k$. $\endgroup$ Commented Oct 4, 2011 at 22:16
  • 3
    $\begingroup$ 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$. $\endgroup$
    – Srivatsan
    Commented Oct 4, 2011 at 22:20
  • $\begingroup$ @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$ $\endgroup$ Commented Oct 4, 2011 at 22:21
  • $\begingroup$ @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. $\endgroup$ Commented Oct 4, 2011 at 22:25
  • $\begingroup$ @3Sphere Yes, now I think I understand what your question really is. :) $\endgroup$
    – Srivatsan
    Commented Oct 4, 2011 at 22:29

4 Answers 4


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


ways to choose the $k$ elements, which we can also write as


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.

  • $\begingroup$ 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$? $\endgroup$ Commented Oct 4, 2011 at 22:40
  • $\begingroup$ Yes, that's right. $\endgroup$ Commented Oct 5, 2011 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.

  • $\begingroup$ 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? $\endgroup$ Commented Oct 5, 2011 at 1:58
  • $\begingroup$ 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.) $\endgroup$
    – Srivatsan
    Commented Oct 5, 2011 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.


A quick expansion on what @Srivatsan mentioned in a comment.

Imagine an array of elements: $[a_1, \dots, a_n]$. Like a MATLAB array, we index starting from 1.

You have n possible "indexes": $\{1, \dots, n\}$

Select $k$ of these $n$ indexes. There's $\binom{n}{k}$ ways to do this, since indexes are unique. As a concrete example, if n=9 and k=5, is $(4,7,2,8,3)$ one of the $\binom{9}{5}$ possible combinations.

Each combination of indexes, is a subset of the set $\{1, \dots, n\}$, which is a set with unique elements. If we sort our combination of indexes, we get the "ordered" k-tuple of indexes: $(i_{1}, ... i_{k}) = (2,3,4,7,8)$. Each combination leads to a unique "ordered" k-tuple of indexes.

If we use these to index the array, we get the corresponding "ordered" k-tuple of elements: $(a_2, a_3, a_4, a_7, a_8)$.

Thus, selection of $k$ indexes $(i_{1}, ... i_{k})$ out of $n$, is equivalent to selecting an "ordered" k-tuple of elements $(a_{i_1}, ... a_{i_k})$. There's $\binom{n}{k}$ ways to do the former, so there's the same number of ways to do the latter.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .