Proving Binomial coefficients identity (SPOJ KOPC12B)

Revision en2, by Medo., 2017-11-06 22:53:30

Hi CF!

I was recently solving this problem : http://www.spoj.com/problems/KOPC12B/

The problem statement is just one line, so no need to rephrase it.

Knowing the solution to the problem without weights, and printing consecutive values, I guessed the answer to be n*C(2n,n)/2 after some trial and error and was surprised it passed.

I tried to arrive at a combinatronics proof by trying to pose the problem as counting binary strings with certain properties, but didn't get somewhere noticeable, I also tried changing (C(n,k)^2) to C(n,k) * C(n,n — k).

Any help proving this? Thanks.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Medo. 2017-11-06 22:53:30 477 (published)
en1 English Medo. 2017-11-05 19:50:01 192 Initial revision (saved to drafts)