I am looking for the combinatorial argument for the identity:

\begin{equation} k\binom{n}{k} = n\binom{n-1}{k-1} \end{equation}

This is easy to show algebraically as:

\begin{equation} \binom{n}{k} = \dfrac{n(n-1)(n-2)(n-k+1)}{k(k-1)!} \end{equation}

  1. What is the combinatorial argument?
  2. What are some general ideas to get started?

Here is a clarification of 2. From what I have seen so far, proving (combinatorially) an identity with an addition sign usually implies that we need to partition a set (this makes sense because of the addition rule and provides a nice visual). On the contrary, the previous observation leads me to believe that multiplication in identities can be resolved with the multiplication principle, but what is the "visual/interpretation" for this? Could someone provide such an interpretation for the example identity given above?


The number of ways of choosing a committee of $k$ members from a group of $n$ people, then selecting one of the $k$ members to be chair, is equal to the number of ways of choosing the chair from out of the whole group of $n$ first, then selecting the $k-1$ other members from among the $n-1$ other people.


The LHS is a product, and one principle is that products count pairs. As $\binom{n}{k}$ is the number of $%k$-subsets of $\{1,\ldots,n\}$, we can interpret the LHS as the number of ordered pairs $(i,S)$ where $S$ is a subset of $\{1,\ldots,n\}$ of size $k$, and $i$ is an element of $S$.

Now we see that we have counted the pairs by choosing first the subset, and then an element from it. If we choose $i$ first, we get a $k$-subset that contains it by choosing a subset of size $k-1$ from $\{1,\ldots,n\}\setminus i$ and adding $i$ to it. So the number of pairs is $n\times \binom{n-1}{k-1}$. (Here we are making use of a bijection between the $k$-subsets that contain $i$ and the $(k-1)$-subsets of $\{1,\ldots,n\}$ that do not contain $i$.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.