# Math Help - Combinatorial proof

1. ## Combinatorial proof

I'm having trouble trying to prove the identity "C(n, m) * C(m, k) = C(n, k) * C(n-k, m-k)" (for 0 <= k <= m <= n where n, m and k are natural numbers), using a combinatorial proof, could someone assist?

Thanks in advance! :-)

2. Originally Posted by posix_memalign
I'm having trouble trying to prove the identity "C(n, m) * C(m, k) = C(n, k) * C(n-k, m-k)" (for 0 <= k <= m <= n where n, m and k are natural numbers), using a combinatorial proof, could someone assist?

Thanks in advance! :-)
L.H.S. = $\frac{n!}{m! (n - m)!} \frac{m!}{k! (m - k)!} = \frac{n!}{(n-m)! (m-k)! k!}$.

R.H.S. = $\frac{n!}{k! (n - k)!} \frac{(n-k)!}{(m - k)! (n-m)!} = \frac{n!}{(m-k)! (n-m)!k!}$.

What do you notice?

3. Originally Posted by mr fantastic
L.H.S. = $\frac{n!}{m! (n - m)!} \frac{m!}{k! (m - k)!} = \frac{n!}{(n-m)! (m-k)! k!}$.

R.H.S. = $\frac{n!}{k! (n - k)!} \frac{(n-k)!}{(m - k)! (n-m)!} = \frac{n!}{(m-k)! (n-m)!k!}$.

What do you notice?
I notice that they are similar of course :-)
But I don't know quite how to formulate it in words; does the example for double counting at Combinatorial proof - Wikipedia, the free encyclopedia use the same logic that should be applied here?

4. Originally Posted by posix_memalign
I notice that they are similar of course :-)
But I don't know quite how to formulate it in words; does the example for double counting at Combinatorial proof - Wikipedia, the free encyclopedia use the same logic that should be applied here?
There are many techniques that can be applied. If all you want to do is prove that the statement is true, what I've done in this instance is probably the simplest approach.

5. Originally Posted by posix_memalign
I'm having trouble trying to prove the identity "C(n, m) * C(m, k) = C(n, k) * C(n-k, m-k)" (for 0 <= k <= m <= n where n, m and k are natural numbers), using a combinatorial proof, could someone assist?

Thanks in advance! :-)
Lets say, there are three boxes N,M and K. N has 'n' distinct balls, M needs 'm' balls from N and finally K needs 'k' balls from M. The total number of ways to do this is of course your left hand side. Here we first gave to M and then to K.

But look at what finally happens...
There are k balls in K which are from M and in turn from N. And there are 'm-k' balls in M from N. (*)

So we can now do the same division with first K and then M. Give 'k' balls to K from N(how many combinations?) and then out of the remaining 'n-k' balls in N, give 'm-k' balls to M(how many combinations?). So the end situation is identical to (*). And the total number of combinations is your R.H.S

So we have counted the same procedure in two different ways.....