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?

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?

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?