Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
2  
You have a very low accept rate. Please go back and accept those answers which were correct and most helpful to you. –  Graphth Mar 13 '12 at 16:54
1  
johhny and @Graphth, would you care to take a look at this answer/question? –  The Chaz 2.0 Mar 13 '12 at 17:22
add comment

2 Answers 2

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|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

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.