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 ^^ ?

  • 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
    ....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 Ni$c$olas's answer also gives the $c$ombinatorial explanation.2012-03-16