COMBINATORICS-2


Prove that

∑j=k .. N-2-k j! / {(j-k)!  k! }   =   (N-k-1)! / {(N-2k-2)!   (k+1)! }
  =   C(N-k-1, k+1) ,

where N≥2k+2. Here C(j,k) denotes the binomial coefficient.

This result follows from the identity (The Art of Computer Programming by Prof. D. Knuth, eq. 1.2.6.11)

∑k=0 .. nC(k, m) = C(n+1, m+1)

Marco Corvi - 2003