# Closed form for alternating combinatoric sum

Is there a closed form for the sum \begin{align} \sum_{k=0}^r (-1)^k \left(\begin{matrix} n-q \\ r - k \end{matrix}\right)\left(\begin{matrix} q \\ k \end{matrix}\right)? \end{align}

Some intuition behind it:

Suppose you have $n$ buckets, and $q$ of them are filled with water. Suppose also that you have a claw machine that always picks out $r$ buckets. Then \begin{align} \left(\begin{matrix} n-q \\ r - k \end{matrix}\right)\left(\begin{matrix} q \\ k \end{matrix}\right) \end{align} is the number of ways to pick out $k$ buckets of water.

I think that combinatorially, it must be true that \begin{align} \sum_{k=0}^r\left(\begin{matrix} n-q \\ r - k \end{matrix}\right)\left(\begin{matrix} q \\ k \end{matrix}\right) = \left(\begin{matrix} n \\ r \end{matrix}\right) \end{align} But I can't work out the case for the alternating sum.

• This alternating sum is actually quite complex. Once, I was trying to look for the $(n,q,r)$ such that $S(n,q,r)=0$. See at math.stackexchange.com/q/1664420 how complicated the pattern of the zeroes of $S(n,q,r)$ can be Apr 18 '17 at 18:29
• Wow, this is quite a discussed problem, and it seems quite non-trivial. Thanks! Before I posted I tried browsing previous stackexchange posts on binomial combinatorics like this but unfortunately it's very hard to exactly articulate the problem in a post title. Apr 18 '17 at 19:02

I don't think so in general, but we can say something. I'll call your sum $S(n,q,r)$. Then $S(n,q,r)$ is the coefficient of $X^r$ in $(1+X)^{n-q}(1-X)^q$, that is $$(1+X)^{n-q}(1-X)^q=\sum_{r=0}^n S(n,q,r)X^r.$$ I don't think there's a simple formula for $S(n,q,r)$ in general, but there are in special cases.
For instance, take $n=2q$. Then $$\sum_{r=0}^n S(2q,q,r)X^r=(1+X)^q(1-X)^q=(1-X^2)^q.$$ So $S(2q,q,r)=0$ for odd $r$ and $S(2q,q,2k)=(-1)^k{q\choose k}$.
Another example is $n=2q+1$. Then $$\sum_{r=0}^n S(2q+1,q,r)X^r=(1+X)^{q+1}(1-X)^q=(1+X)(1-X^2)^q.$$ Then $S(2q+1,q,2k)=S(2q+1,q,2k+1)=(-1)^k{q\choose k}$.