# Combinatorial Identity

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.

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

-