2

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

JMoravitz
  • 79,518
pyschedelicsid
  • 99

1 Answers1

6

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.

JMoravitz
  • 79,518
  • 2
    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? – pyschedelicsid Sep 26 '17 at 17:33
  • 2
    @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$ – JMoravitz Sep 26 '17 at 17:39