2
$\begingroup$

Is there any combinatorial intuition to prove this identity $r\cdot \binom{n}{r}=n\cdot\binom{n-1}{r-1}$?

$\endgroup$
6
$\begingroup$

Hint: Consider forming a committee from a group of $n$ people where one member of the committee is special, e.g. the chairman of the committee. Try counting this in two different ways.

$\endgroup$
  • 2
    $\begingroup$ Okay, I think I got it. Like first we choose the chairman out of n people in n ways and then the rest r-1 from n-1, in n-1 choose r-1. The other way is first we choose r people in, n choose r and then select the chairperson out of those r selected. Am I right? $\endgroup$ – pyschedelicsid Sep 26 '17 at 17:33
  • 2
    $\begingroup$ @pyschedelicsid yes. The same logic will show the more general identity $\binom{n}{r}\binom{r}{k}=\binom{n}{k}\binom{n-k}{r-k}$, your specific case is where $k=1$ $\endgroup$ – JMoravitz Sep 26 '17 at 17:39

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.