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.


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.

| cite | improve this answer | |
  • $\begingroup$ Nice answer. Thank you. $\endgroup$ – Med Mar 24 '16 at 15:08
  • $\begingroup$ @Med: You’re welcome. $\endgroup$ – Brian M. Scott Mar 24 '16 at 15:09
  • $\begingroup$ That third step was just wow! $\endgroup$ – Cloverr Mar 24 '16 at 15:14

Just one more flavor of Vandermonde’s identity. $$ \sum_k \binom{l}{k+m}\binom{s}{k+n} = \binom{l+s}{l-m-n} $$ Then the original sum for $l=i$,$s=N-i$,$m=1$, and $n=0$ gives: $$ \sum_{j=0}^{i-1} \binom{i}{j+1}\binom{N-i}{j} = \binom{N}{i-1} $$

| cite | improve this answer | |

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.