2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – René Gy
    Apr 18 '17 at 18:29
  • $\begingroup$ 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. $\endgroup$
    – Paradox
    Apr 18 '17 at 19:02
2
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.