1
$\begingroup$

I'm new to the discrete math, but I'm trying to prove this algebraically and some help would be cool.

$$ \binom{a}{b} \binom{b}{c}= \binom{a}{c} \binom{a-c}{b-c},\quad c \leqslant b \leqslant a $$

I'm not sure how to prove this algebraically. Can someone help me?

So after some work i got

$$ \frac{a!}{(a-b)!} \cdot {c! \cdot (b-c)!} = \frac{a!}{c! } \cdot {(b-c)! \cdot (a-c -(b-c))!} $$

How much more can i simplify this ^^ ?

  • 1
    Maybe you know some formula for $ \binom{a}{b} $?2012-03-16
  • 0
    I actually think the combinatorial rather than algebraic way of looking at it is more enlightening. Sasha's answer and the one hinted at by AD, are not the way I would do it. See my answer below.2012-03-16

3 Answers 3

2

Recall the definition $\binom{n}{k} = \frac{n!}{k! \cdot (n-k)!}$, and use it for both sides of the equality: $$ \frac{a!}{b! \cdot (a-b)!} \cdot \frac{b!}{c! \cdot (b-c)!} = \frac{a!}{c! \cdot (a-c)!} \cdot \frac{(a-c)!}{(b-c)! \cdot (a-c -(b-c))!} $$ Expanding $(a-c-(b-c))= (a-b)$ and cancelling $b!$ in the numerator and the denominator on the left-hand-side, and the $(a-c)!$ in the numerator and the denominator on the right-hand-side, you obtain the desired equality.

  • 0
    Oh so basically call the n choose k definition and work off of it? but how about the right side basically the same thing right?2012-03-16
  • 0
    I find bijective arguments more illuminating than things like this. Maybe that's just me.... But still it's worth knowing both.2012-03-16
  • 0
    ....and now I've posted a combinatorial argument below, and I see that someone else has also posted that same argument.2012-03-16
2

In addition to the algebraic calculation that you asked for, there is a combinatorial explanation of the result. We have a class of $a$ students. We want to pick $b$ lucky students from this class to give a chocolate bar to, and choose $c$ of the lucky students to give an additional chocolate bar to. In how many ways can we do this? Here are two ways of counting:

First count: There are $\binom{a}{b}$ ways to choose the students who will get at least one chocolate bar. For every one of these ways, there are $\binom{b}{c}$ ways to choose the subgroup of $c$ students who will get an additional chocolate bar, for a total of $\binom{a}{b}\binom{b}{c}$.

Second count: Pick the $c$ students who will get $2$ chocolate bars first. There are $\binom{a}{c}$ ways to do this. Now pick an additional $b-c$ students from the remaining $a-c$ to give $1$ chocolate bar to. There are $\binom{a}{c}$ ways to pick the twice lucky students, and for every one of these ways, there are $\binom{a-c}{b-c}$ ways to pick the single chocolate bar students, for a total of $\binom{a}{c}\binom{a-c}{b-c}$ ways.

We counted something in two different ways. So the answers must be the same. But that gives precisely your formula.

2

Saying you're going to choose a committee of $b$ members out of a group of $a$ members, and then you'll choose a subcommittee of $c$ members out of the committee of $b$ members. The number of ways to do that is $$\binom{a}{b} \binom{b}{c}.$$

But alternatively, you could first choose $c$ members out of $a$, who will be on the subcommittee, and then choose the other members of the committee, of whom there must be $b-c$, out of the remaining $a-c$ candidates. The number of ways to do that is $$\binom{a}{c} \binom{a-c}{b-c}.$$

  • 0
    +1. Andre Nicolas's answer also gives the combinatorial explanation.2012-03-16