varice2r

2022-09-14

Show that $\left(n-r\right)\left(\genfrac{}{}{0}{}{n+r-1}{r}\right)\left(\genfrac{}{}{0}{}{n}{r}\right)=n\left(\genfrac{}{}{0}{}{n+r-1}{2r}\right)\left(\genfrac{}{}{0}{}{2r}{r}\right)$.
In the LHS $\left(\genfrac{}{}{0}{}{n+r-1}{r}\right)$ 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 $\left(n-r\right)$ players.
The RHS divides up a team into $2$ sets?

Dalton Erickson

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 $\left(n-r\right)\left(\genfrac{}{}{0}{}{n}{r}\right)=n\left(\genfrac{}{}{0}{}{n-1}{r}\right)$ 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\left(\genfrac{}{}{0}{}{n-1}{r}\right)\left(\genfrac{}{}{0}{}{n+r-1}{r}\right)$, 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 $2r$).
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.

cubanwongux

Dividing the LHS by the RHS and expanding the definition of the choose notation, we have
$\left(n-r\right)\frac{\left(n+r-1\right)!}{r!\left(n-1\right)!}\frac{n!}{r!\left(n-r\right)!}\cdot \frac{1}{n}\frac{\left(2r\right)!\left(n-r-1\right)!}{\left(n+r-1\right)!}\frac{r!r!}{\left(2r\right)!}.$
By cancelling appropriately, it follows that the LHS divided by the RHS is $1$, so they're equal.

Do you have a similar question?