3
$\begingroup$

Problem Statement

Seven women and nine men are on the faculty in the mathematics department at a school. How many ways are there to select a committee of five members if at least one woman must be on the committee?

Solution I

My first thoughts to solve this problem were to find out how many possible combinations of committees could be formed from the given population. I then subtracted from this the total number of committees that could be formed of all men.

${16 \choose 5} - {9 \choose 5} = 4242$

On most platforms, this seems to be the consensus on what is the correct answer.

Solution II

Out of curiosity, I tried to solve the problem from a different angle. Assume we choose an arbitrary woman from the population of women faculty members as the first committee member. Now there are 6 women and 9 men in the remaining population. Now that at least one woman is guaranteed to be on the committee, the total number of committees that can be formed is the number of possible combinations of the remaining four spots, which is

${15 \choose 4} = 1365$

Obviously, this approach reveals a significantly smaller number of possible combinations, so my question is what went wrong?

$\endgroup$
5
$\begingroup$

The first solution is correct.

There are a couple of things wrong with the second solution. First, there are $7$ ways to chose the first woman, and your solution doesn't reflect this. Second, if we multiply by $7$ we will be double counting, since picking Alice and then Betty is the same as picking Betty, then Alice.

If you want to do it directly, that is, without subtraction, the easiest way will be to count the committees with exactly one woman, exactly two women, and so on. $$\sum_{w=1}^5\binom 7w\binom 9{5-w}$$

The first calculation is simpler and less error-prone.

$\endgroup$
5
  • $\begingroup$ Your sum is nearly correct, but you've failed to account for the fact that you're actually triple-counting cases with three women, since you count once letting each woman be the first woman you chose. But as you pointed out, this is exactly why the first solution is preferred, it's much less error-prone. $\endgroup$ – Stephen Donovan Apr 14 at 4:46
  • $\begingroup$ @StephenDonovan That's completely wrong. Binomial coefficients count combinations, not permutations. Look here $\endgroup$ – saulspatz Apr 14 at 4:51
  • $\begingroup$ Oh pardon me, I misread your answer. I thought we went down the same line of reasoning of correcting the first answer, if you look at my answer you might understand my confusion $\endgroup$ – Stephen Donovan Apr 14 at 4:52
  • $\begingroup$ My apologies, the series just look very similar so I got confused $\endgroup$ – Stephen Donovan Apr 14 at 5:23
  • $\begingroup$ Thank you so much! $\endgroup$ – Lolitarox33 Apr 14 at 15:15
5
$\begingroup$

I think the issue arises from the fact that you haven't accounted for the $7$ ways to choose who the first woman you put in is, so for instance any of the cases where you have one woman and a specific choice of four men are counted the same.

You can multiply by $7$ to remedy this, but then you would get a lot of double-counting in the cases where there is more than one woman. In general, you would be counting cases with $n$ women $n$ times, once where each woman was the first woman you chose. So our total overcounting after multiplying by $7$ is $\Sigma_{k=1}^{5}(k-1)\binom{7}{k}\binom{9}{5-k}$, because the $\binom{7}{k}\binom{9}{5-k}$ gives the number of possible committees with $k$ women, the $(k-1)$ is the number of times we overcount each case, and we add up over all the possible numbers of women we can have in the committee.

Doing this correction you would get $7(1365) - \binom{7}{2}\binom{9}{3} - 2\binom{7}{3}\binom{9}{2} - 3\binom{7}{4}\binom{9}{1} - 4\binom{7}{5}\binom{9}{0} = 4242,$ which is the correct answer.

$\endgroup$
2
  • $\begingroup$ Thank you so much! $\endgroup$ – Lolitarox33 Apr 14 at 15:05
  • $\begingroup$ No problem, have a nice day $\endgroup$ – Stephen Donovan Apr 14 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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