Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

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

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.


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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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