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}
- What is the combinatorial argument?
- 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?
Answer
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.
No comments:
Post a Comment