Show that (n−r)(n+r−1 r)(n r)=n(n+r−1 2r)(2r r). In the LHS (n+r−1r) counts the number of ways of selecting r objects from a set of size n where order is not significant and repetitions are allowed. So you have n people you form r teams and select r captains and select (n−r) players. The RHS divides up a team into 2 sets?
Show that .
In the LHS counts the number of ways of selecting objects from a set of size where order is not significant and repetitions are allowed. So you have people you form teams and select captains and select players.
The RHS divides up a team into sets?
Answer & Explanation
Let be a set of elements. Both sides count the number of ways to select two disjoint sets of size and possibly an element .
We first observe that as both sides count the number of ways to form a team of size with a captain out of people.
Applying the above on the original LHS we get , which corresponds to selecting ( out of ), then ( out of the remaining ) and ( choices in and one option of not choosing ).
The RHS argument goes as follows: choose elements for both and , then choose of them to make . Then, as before, there are options of choosing or none at all.
Dividing the LHS by the RHS and expanding the definition of the choose notation, we have
By cancelling appropriately, it follows that the LHS divided by the RHS is , so they're equal.