3
$\begingroup$

For any integers $n$, $k$, $r$ where $n\geq k\geq r \geq 0$, give a combinatorial proof of the following identity: \begin{align} \binom{n}{k}\binom{k}{r}=\binom{n}{r}\binom{n-r}{k-r} . \end{align}

The problem is that I can't come up with a good counting argument of what exactly the two sides are doing. The left hand side is quite mysterious, and the right hand side is apparently choosing $r$ items and then choosing $k-r$ items from the remaining, which should be equivalent to $\binom{n}{k}$ but somehow isn't. How should I approach this problem?

$\endgroup$
  • 1
    $\begingroup$ I think the reason the RHS is not $\binom{n}{k}$ is that in choosing $r$ items and then $k-r$ items, you can distinguish between the items chosen in the first batch and those chosen in the second. $\endgroup$ – Alex Becker May 11 '13 at 14:46
6
$\begingroup$

Think of the problem of how to choose a sports team team consisting of $k$ people, and then to choose $r$ people from that team to play in a particular match (leaving $k-r$ people on the sidelines). How many ways are there to do this if you have $n$ total people from which to choose?

We can make these choices in two different ways. First of all, how many ways are there to pick the entire team first, and then pick the players for the match from the team? Secondly, how many ways are there to pick just the players for the match first, and then fill out the rest of the team from the people you didn't pick?

In more general terms, we you can think of this identity as saying that if we make a selection from a set of $n$ things so that $k$ of them have a property $1$ and $r$ of them have properties $1$ and $2$, it doesn't matter the order in which we assign the properties.

$\endgroup$
  • 1
    $\begingroup$ Good way of explaining this. That is, let $A$ be a set with $n$ elements. You are counting the pairs $(B, C)$, where $B \subseteq C \subseteq A$, with $\lvert B \rvert = r$, and $\lvert C \rvert = k$, in two ways, either $C$ first (LHS), or $B$ first (RHS). $\endgroup$ – Andreas Caranti May 11 '13 at 14:51
  • $\begingroup$ @AndreasCaranti Thank you! It's probably my favourite combinatorial proof! I'm never quite sure how generally to phrase a proof to be both understandable and to make sure it applies to all related situations, but the subset terminology is nice. $\endgroup$ – Tom Oldfield May 11 '13 at 14:56
  • $\begingroup$ I'm not failing to get the identity. How can we formalize this? How can the left hand side be formulated into the size of a set $S$? $\endgroup$ – ithisa May 11 '13 at 15:00
  • 1
    $\begingroup$ @EricDong, look at my comment, it is the set of all pairs $(B, C)$ etc. $\endgroup$ – Andreas Caranti May 11 '13 at 15:01
2
$\begingroup$

You have $n$ children. Give $k$ of them plates, and on $r$ of those plates, put a cookie. That gives you the left hand side.

Now, with the same $n$ children, give $r$ of them a plate with a cookie. Of the $n-r$ children that don't have a plate with a cookie, give $k-r$ of them empty plates. This gives you the right hand side.

$\endgroup$
0
$\begingroup$

Choose a $k$-member team (from $n$ people) and then choose an $r$-member starting line up. That gives you the LHS. Now do the same thing in a different way. Choose the $r$-member starting line up first then choose the $k-r$ member substitution from the remaining $n-r$ people. This gives you the RHS.

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