Combinatorial Proof of ${n\choose{m}}=\frac{n}{m}{{n-1}\choose{m-1}}$

334 Views Asked by At

How do prove the following identity combinatorially? $${n\choose{m}}=\frac{n}{m}{{n-1}\choose{m-1}}$$

Any help or hints would be great!

2

There are 2 best solutions below

0
On BEST ANSWER

Since selecting $m$ out of $n$ people and giving one of the selected a hat is the same as selecting one hat.bearer out of $n$ people and then picking $m-1$ from the remaining $n-1$ people, we have $m{n\choose m}=n{n-1\choose m-1}$.

0
On

Hint: Choose a committee of $m$ people among a total of $n$ people, then in the committee, we choose a chairman, for example.