Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Show that $(n-r) \binom{n+r-1}{r} \binom{n}{r} = n \binom{n+r-1}{2r} \binom{2r}{r}$.

In the LHS $\binom{n+r-1}{r}$ 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?

share|improve this question
add comment

2 Answers

up vote 5 down vote accepted

Let $S$ be a set of $n+r-1$ elements. Both sides count the number of ways to select two disjoint sets $A,B\subseteq S$ of size $r$ and possibly an element $c\in S \setminus B$.

We first observe that $(n-r)\binom{n}{r}=n\binom{n-1}{r}$ as both sides count the number of ways to form a team of size $r+1$ with a captain out of $n$ people.

Applying the above on the original LHS we get $n\binom{n-1}{r}\binom{n+r-1}{r}$, which corresponds to selecting $A$ ($r$ out of $n+r-1$), then $B$ ($r$ out of the remaining $n-1$) and $c$ ($n-1$ choices in $S\setminus B$ and one option of not choosing $c$).

The RHS argument goes as follows: choose $2r$ elements for both $A$ and $B$, then choose $r$ of them to make $B$. Then, as before, there are $n$ options of choosing $c\in S\setminus B$ or none at all.

share|improve this answer
    
Starting with $n+r-1$ & maybe picking someone NOT on one team & using alg identity is overly complicated. Simpler: start with $n+r$, $n$ can be umpire, $r$ cannot. RHS: pick ump, then from $n+r-1$ left, pick $2r$ & divide them into 2 teams of $r$. LHS: pick the ump, then pick $r$ from $n+r-1$ left to be on a team. From the $n$ not on team one, pick $r$ to be on team 2. Whoops, our ump might be on team two. Forget him for a bit (divide by $n$). Pick someone from the $n-r$ left. If he can be ump, good. Otherwise swap him with the orig ump. All combos from RHS can be gotten this way. –  Travis Bemrose Oct 22 '12 at 11:45
add comment

I don't claim to have a slick combinatorial proof, but I've upvoted the question in hopes that someone will provide one.

I would cop out and show equality as follows. Dividing the LHS by the RHS and expanding the definition of the choose notation, we have $$ (n-r)\frac{(n + r - 1)!}{r!(n-1)!} \frac{n!}{r!(n-r)!} \cdot \frac{1}{n} \frac{(2r)!(n-r-1)!}{(n+r-1)!} \frac{r!r!}{(2r)!}.$$

By cancelling appropriately, it follows that the LHS divided by the RHS is 1, so they're equal.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.