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'm having trouble figuring out why these two different ways to write this combination give different answers. Here is the scenario:

Q: Choose a group of 10 people from 17 men and 15 women, in how many ways are at most 2 women chosen?

Solution A: From 17 men choose 8, and from 15 women choose 2. Or from 17 men choose 9, and from 15 women choose 1. Or from 17 men choose 10.

C(17,8)*C(15,2)+C(17,9)*C(15,1)+C(17,10) = 2936648 ways

Solution B: Choose from the men to fill the first 8 positions and choose the next 2 positions from the remaining men and women.

C(17,8)*[C(9,2)+C(9,1)*C(14,1)+C(14,2)] = 6150430 ways

What is wrong with my logic or interpretation here?

share|cite|improve this question
2  
The second method over counts. Specifically, if $X$ is one of the men, then you might choose him out of the first $8$ or you might choose him in the next two. – lulu Jan 10 at 0:31
    
The second way count some examples multiple times. – Thomas Andrews Jan 10 at 0:37
up vote 4 down vote accepted

Suppose that the men are $M_1,\ldots,M_{17}$, and the women are $W_1,\ldots,W_{15}$. Consider the group

$$\{M_1,M_2,\ldots,M_9,W_1\}\;.$$

Your second approach counts this $9$ times: once as $\{M_1,\ldots,M_8\}$ for the $8$ men and $\{M_9,W_1\}$ for the last two, once as $\{M_1,M_2,M_3,M_4,M_5,M_6,M_7,M_9\}$ for the $8$ men and $\{M_8,W_1\}$ for the last two, and so on. It does this overcounting for every group that contains exactly one woman.

Groups that contain no women are overcounted even more: for any group of $10$ men, there are $\binom{10}2=45$ different ways to split it into the first $8$ and the last $2$, so it gets counted $45$ times!

share|cite|improve this answer

Consider a simpler problem. How many ways are there to choose ten men from a set of ten men? By your second reasoning, choose eight first, then choose another two. That gives a total of: $$\binom{10}{8}\binom{2}{2}=45$$ Why is that reasoning problematic?

share|cite|improve this answer

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.