Thursday, 6 October 2011

co.combinatorics - alternating sums of terms of the Vandermonde identity

So, you are interested in $f(n,k)=sum_{i=0}^k (-1)^ibinom{k}{i}binom{2n-k}{n-i}$.
Simple manipulations show $f(n,k)=frac{k!(2n-k)!}{(n!)^2}left[sum_{i=0}^n (-1)^i binom{n}{i}binom{n}{k-i}right]$
Now the second factor counts the coefficient of $x^k$ in $(1-x^2)^n$ and therefore if $k$ is odd $f=0$ otherwise $f=(-1)^{frac{k}{2}}frac{k!(2n-k)!}{n!(k/2)!(n-k/2)!}$ which is far from zero...



EDIT: On a different note I see the result is a signed generalized Catalan number of degree 2 (I was not aware they satisfied such simple identities). Since usually providing combinatorial interpretations for generalized Catalan numbers is not easy, may I ask in what combinatorial context did you face the above calculation?

No comments:

Post a Comment