Combinatorial proof help please!

Mar 2009
13
0
C (m+n , r) = C(n,0) *C(m , r) + C(n , 1) * C(m, r-1) + ...... + C(n , r) * C(m , 0) give combinatorial argument for it. (I did not write the parantez


C(n , k) = C(k-1 , k-1) + C(k , k-1) + ........ + C(n-1 , k-1) give combinatorial argument for it. (I did not write the parantez
 

GCD

Jan 2009
14
0
Well it's quite simple, which might look as a lot of hand waving but non the less. :mrgreen:

1. C (m+n , r) = C(n,0) *C(m , r) + C(n , 1) * C(m, r-1) + ...... + C(n , r) * C(m , 0)
For C(m+n,r) you might choose r from m items and none from the n terms, or 1 from the n items and r-1 from the m items, etc.

2. C(n , k) = C(k-1 , k-1) + C(k , k-1) + ........ + C(n-1 , k-1)
Well you wanted combinatorial method, so here you have it:
http://binomial.csuhayward.edu/proofs/pf1100002.html

There's also algebraic method, can't recall how it goes, thoguh.