Thursday, September 27, 2018

combinatorics - Combinatorial argument for the identity $kbinom{n}{k} = nbinom{n-1}{k-1}$


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?


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

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...