1
$\begingroup$

The problem is as follows:

The dean of science wants to select a committee consisting of mathematicians and physicists to discuss a new curriculum. There are $15$ mathematicians and $20$ physicists at the faculty; how many possible committees of $8$ members are there, if there must be more mathematicians than physicists (but at least one physicist) on the committee?

The given solution splits up the choices into the cases where there is $1$ physicist, $2$ physicists, and $3$ physicists. Then it's simply a matter of summing up $\binom{15}{5}\cdot\binom{20}{3}$ and $\binom{15}{6}\cdot\binom{20}{2}$ and $\binom{15}{7}\cdot\binom{20}{1}$, giving $4503070$.

This is what I tried to do: first I pick a physicist, making sure I have at least one on the team. I have $20$ choices for this. Then I pick $5$ mathematicians, making sure there are more mathematicians than physicists on the team. I have $15\cdot14\cdot13\cdot12\cdot11$ choices for this. Then I pick two people from the $29$ people that are left because it doesn't matter whether they are mathematicians or physicists. I have $29\cdot28$ choices for this. After I multiply all those numbers, I need to divide by the number of ways I can permutate them, because order doesn't matter. I get $$\dfrac{20\cdot15\cdot14\cdot13\cdot12\cdot11\cdot29\cdot28}{8!} = 145145,$$ which is obviously not the right solution. Where did I go wrong?

Thanks in advance.

$\endgroup$
  • 2
    $\begingroup$ It's the permuting that does it wrong. If you have, for example, 3 p and 5 m, you'll have 6 permutations from the p and 120 from the m, giving 720 permutations, not 8!. So I'm afraid you'll have to split up after all $\endgroup$ – Ronald Aug 17 '18 at 10:31
  • $\begingroup$ There is another issue here, by designating a particular physicist as belonging to the committee, you count committees with more than one physicist multiple times. Similarly, by designating a particular set of five mathematicians as belonging to the committee, you count committees with more than five mathematicians multiple times. $\endgroup$ – N. F. Taussig Aug 18 '18 at 8:00
  • $\begingroup$ @N.F.Taussig I see. So is there no way to solve this kind of problem using designations? $\endgroup$ – Surzilla Aug 18 '18 at 15:06
  • $\begingroup$ I have added an answer which analyzes the errors you made. $\endgroup$ – N. F. Taussig Aug 18 '18 at 22:18
1
$\begingroup$

You made a calculation error. $$\frac{20 \cdot 15 \cdot 14 \cdot 13 \cdot 12 \cdot 11 \cdot 29 \cdot 28}{8!} = \color{red}{1161160}$$ Let's examine your numerator: $$20 \cdot 15 \cdot 14 \cdot 13 \cdot 12 \cdot 11 \cdot 29 \cdot 28 = 20 \cdot \frac{15!}{10!} \cdot \frac{29!}{27!} = \binom{20}{1} \cdot \binom{15}{5} \cdot 5! \cdot \binom{29}{2} \cdot 2!$$ Since the order in which we choose the five designated mathematicians does not matter, we should divide your numerator by $5!$. Since the order in which the two additional committee members does not matter, we should also divide your numerator by $2!$. Doing so yields $$\binom{20}{1}\binom{15}{5}\binom{29}{2} = 24384360 = \frac{8!}{5!2!} \cdot 1161160$$ which is too large.

Let's see why.

A committee of eight people drawn from $20$ physicists and $15$ mathematicians that contains a majority of mathematicians but at least one physicist must contain either five mathematicians and three physicists or six physicists and two physicists or seven mathematicians and one physicist. The number of ways of selecting exactly $k$ mathematicians and $8 - k$ physicists from the $15$ mathematicians and $20$ physicists is $$\binom{15}{k}\binom{20}{8 - k}$$ Hence, the number of admissible committees is $$\binom{15}{5}\binom{20}{3} + \binom{15}{6}\binom{20}{2} + \binom{15}{7}\binom{20}{1} = 450370$$ By designating a particular physicist as the physicist on the committee, you count each committee with $p$ physicists $p$ times, once for each way you could designated one of them as the designated physicist. By designating five of the mathematicians on the committee as the five designated mathematicians on the committee, you count each committee with $m$ mathematicians $\binom{m}{5}$ times, once for each way you could designate five of the $m$ mathematicians as the designated mathematicians. Observe that $$\binom{20}{1}\binom{15}{5}\binom{29}{2} = \color{red}{\binom{5}{5}\binom{3}{1}}\binom{15}{5}\binom{20}{3} + \color{red}{\binom{6}{5}\binom{2}{1}}\binom{15}{6}\binom{20}{2} + \color{red}{\binom{7}{5}\binom{1}{1}}\binom{15}{7}\binom{20}{1}$$

$\endgroup$
  • 1
    $\begingroup$ I understand now. Thanks a lot for taking the time to write this comprehensive answer! $\endgroup$ – Surzilla Aug 19 '18 at 7:21
  • $\begingroup$ But should't it be "By designating a particular physicist as the physicist on the committee, you count each committee with $p$ physicists $\color{red}{p!}$ times"? $\endgroup$ – Surzilla Aug 19 '18 at 7:28
  • $\begingroup$ No. Imagine the physicists on the committee are Einstein, Bohr, and Planck. We count the committee once when we designate Einstein as the physicist and Bohr and Planck as the additional members, once when we designate Bohr as the physicist and Einstein and Planck as the additional members, and once when we designate Planck as the physicist and Einstein and Planck as the additional members. Notice that we have counted the committee three times, not $3! = 6$ times. $\endgroup$ – N. F. Taussig Aug 19 '18 at 7:32
  • $\begingroup$ Oh, I thought we counted Bohr,Planck and Planck,Bohr double. $\endgroup$ – Surzilla Aug 19 '18 at 7:36
  • $\begingroup$ The reason I chose a committee with three physicists is that we do count a committee with two physicists twice. Since $2! = 2$, I can see how you could be misled into thinking that we count each committee with $p$ physicists $p!$ times if you did not consider committees with three physicists. $\endgroup$ – N. F. Taussig Aug 19 '18 at 7:39
2
$\begingroup$

You don't have $8!$ possible permutations. For instance, the first person you chose can never be a mathematician and the second, third, fourth, fifth and sixth persons you chose can never be physicists.

$\endgroup$
0
$\begingroup$

You want to choose a committee of 8 members given that no of mathematcians should be greater than physicists and choose at least 1 physicists. Here are the possibilities I am representing mathematicians by M and physicists by P $$7 M 1 P$$ $$6 M 2 P$$ $$5 M 3 P$$

$$total=\binom{15}{7}\binom{20}{1}+\binom{15}{6}\binom{20}{2}+\binom{15}{5}\binom{20}{3}$$

$\endgroup$
  • 1
    $\begingroup$ The OP already knows the correct answer. The question is why the OP's method did not work. $\endgroup$ – N. F. Taussig Aug 17 '18 at 10:37
  • $\begingroup$ OP is making his selection very complicated he just need to select wisely. $\endgroup$ – Deepesh Meena Aug 17 '18 at 10:39

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.