# Combinatorial proof for $a(n-a) \binom{n}{a} = n(n-1) \binom{n-2}{a-1}$

Prove $$a(n-a) \binom{n}{a} = n(n-1) \binom{n-2}{a-1}$$ by a combinatorial proof.

This is what I tried:

There is a set $$X$$ of $$n$$ elements. There is a subset $$Y$$ of $$a$$ elements.

LHS, we choose 1 element from $$Y$$. Then choose 1 element not from $$Y$$. And choose $$a$$ elements from $$X$$.

RHS, we choose 2 elements from $$X$$, one of which is from $$Y$$ and the other is not from $$Y$$. Then choose $$a-1$$ elements from the remaining elements of $$X$$.

But the way I understand it, we end up with $$2 + a$$ elements on the LHS, while we end up with $$2+a-1$$ elements on the RHS.

• What you're missing on the LHS: those $a$ elements you chose from $X$? They can be your set $Y$! In other words, the LHS is counting the number of ways of choosing a subset $Y$ of $a$ elements of $X$, along with one element inside $Y$ and one element outside $Y$. – Steven Stadnicki Oct 17 '13 at 22:27

Suppose that you have a group of $n$ players. The lefthand side is the number of ways to pick a team of $a$ of these players, designate one member of the team as captain, and then pick one reserve player from the remaining $n-a$ people. The righthand side is the number of ways to pick the captain, then the reserve player, and then the other $a-1$ members of the team.
Consider the following sets of data $(y,x,Y)$ where $Y\subseteq X$ with $|Y|=a$, $\ y\in Y$ and $x\notin Y$.
Then both side counts this set. For the right hand side, we regard these as data $(a,b,Y')$ with $|Y'|=a-1$ and $a,b\notin Y$, and convert them by $Y':=Y\setminus\{y\}$ and $Y:=Y'\cup\{a\}$.