Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer

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$.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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