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?


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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Travis Bemrose Oct 22 '12 at 11:45

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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