COMBINATORICS-1


Prove that, for N≥M≥n and (N-M)≥n,

∑x=0 .. n C(M, x) C(N-M, n-x) = C(N, n)

where C(a,b) = a! /(b! (a-b)! ) is the binomial coefficient.

This is one of the basic identities concerning sum of products of binomial coefficients: see the book The Art of Computer Programming (by Prof. Knuth) eq. 1.2.6.21.

Marco Corvi - 2003