[Math] Sum of the product of two combination

combinations

Here is a problem: I have $i$ red marbles, which are all different and $N-i$ blue marbles, which are also all different. Let's assume that $i<N-i$ (there are more blue marbles than red marbles). In how many ways can we choose $x$ number of red and $y$ number of blue marbles, so $x$ and $y$ satisfy $x-y=1$?

I have found a formula for this problem, which seems to be correct (please let me know if I am wrong).

$\sum\limits_{j=0}^{i-1}{i \choose j+1}{n-i \choose j} $

I am interested to know if there is a closed-form expression to this answer.

Thanks in advance.

Best Answer

Your formula is correct, and it can be reduced to a closed form:

$$\begin{align*} \sum_{j=0}^{i-1}\binom{i}{j+1}\binom{n-i}j&=\sum_{j=0}^{i-1}\binom{i}{j+1}\binom{n-i}{n-i-j}\\ &=\sum_{j=1}^i\binom{i}j\binom{n-i}{n-i+1-j}\\ &=\sum_{j=0}^i\binom{i}j\binom{n-i}{n-i+1-j}-\binom{i}0\binom{n-i}{n-i+1}\\ &=\sum_{j=0}^i\binom{i}j\binom{n-i}{n-i+1-j}-0\\ &=\binom{n}{n-i+1}\\ &=\binom{n}{i-1} \end{align*}$$

by Vandermonde’s identity.

You can look at it like this: you choose $j$ of the blue marbles to keep and $i-(j+1)$ of the red marbles not to keep, so in every case you’re choosing a total of $i-1$ marbles from the total collection of $n$ marbles. Conversely, if you start with any $i-1$ of the $n$ marbles, let $j$ be the number of them that are blue. You’re going to keep the $j$ blue marbles, so $y=j$. The remaining $i-1-j$ are red, and those are the red ones that you’re really planning not to choose for your final selection of $x$ red marbles, so $x=i-(i-1-j)=j+1=y+1$, as desired.

Related Question