# hypergeometric proof

I've been looking at hypergeometric probability problems and came across this equation. Can someone explain to me why $\sum_{j=0}^{n-1}\frac{\binom{M-1}{j}\binom{(N-1)-(M-1)}{(n-1)-j}}{\binom{N-1}{n-1}}=1$? Take into consideration that I am using $N, M, n$ as parameters where there are $N$ total objects with $M$ "special" or unique objects, and $n$ is a selection sample.

-
johhny and @Graphth, would you care to take a look at this answer/question? – The Chaz 2.0 Mar 13 '12 at 17:22

There is a group of $N-1$ kids, of whom $M-1$ are male. You choose at random a group of $n-1$ kids. The generic term $$\frac{\binom{M-1}{j}\binom{(N-1)-(M-1)}{(n-1)-j}}{\binom{N-1}{n-1}}$$ in your sum is the probability that exactly $j$ of the chosen kids are male. You are summing these probabilities from $j=0$ to $j=n-1$, that is, over all conceivable outcomes for the number of males. The sum of these probabilities must be $1$.

Remark: The calculation remains correct even if, for example, the number $M-1$ of males is a fair bit below $n-1$. For we use the standard convention that $\binom{M-1}{j}=0$ if $j>M-1$.

-

You can prove it combinatorially. First multiply both sides by $\binom{N-1}{n-1}$. You can do this because that does not depend on $j$.

For simplicity, let's say there are $M-1$ special objects and $N-1$ total objects.

The right hand side counts the number of ways to choose $n - 1$ things from $N - 1$ things.

$$\binom{N-1}{n-1}$$

Now, the left hand side counts the same thing

$$\sum_{j=0}^{n-1} \binom{M-1}{j}\binom{(N-1)-(M-1)}{(n-1)-j}$$

But, the left hand side splits it up into cases. When you select $n-1$ things, you will get $j$ of the $M-1$ special objects, as well as $(n-1) - j$ from the rest of the set, which has $(N-1) - (M-1)$ objects in it. Now, $j$ ranges from 0 to $n-1$. So, add up all these counts to get the left hand side. That is, you could get 0 objects from the M, or you could get 1 object from the M, ..., or you could get n-1 objects from the M. So, to count the total number of ways to do the selection, you need to add up these possibilities.

If you want things to match up with what you're saying, then it would be

$$\sum_{j=0}^{n} \binom{M}{j}\binom{N-M}{n-j} = \binom{N}{n}$$

The explanation would be exactly the same, except there would be $N$ total objects, $M$ special objects, and you're choosing $n$ of them. It's simpler this way because there are none of the $-1$'s.

-