1

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.

Med
  • 2,530

2 Answers2

3

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.

Brian M. Scott
  • 616,228
0

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

nickchalkida
  • 1,495