Friday, May 5, 2017

combinatorics - Prove by a combinatorial argument that $(n-r){n choose r}=n{n-1 choose r}$





Prove by a combinatorial argument $$(n-r){n \choose r}=n{n-1 \choose r}$$




My attempt:



We have two ways of count the number of persons forms a committee of a group $n$ of people.



Here I'm a little confused, because I don't know how interpret the multiplication by $(n-r)$ here. Can someone help me?


Answer




On the RHS




  • we choose one president ($n$ choiches) and then form a committee of $r$ out of n-1



On the LHS




  • we form a committee of $r$ out of $n$ and then choose a president from the others $n-r$



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...