3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Steven Stadnicki Oct 17 '13 at 22:27
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks! I think the order of the terms on the left side threw me off. $\endgroup$ – Frank Epps Oct 17 '13 at 22:30
  • $\begingroup$ @Frank: You’re welcome! $\endgroup$ – Brian M. Scott Oct 17 '13 at 22:32
0
$\begingroup$

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\}$.

$\endgroup$

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.