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! :-)
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?
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.....