Combinatorics problem, right solution?

Question

We have $6$ lawyers, $7$ engineers and $4$ doctors. We plan on making a committee of $5$ people, and we want at least one person of each profession on board. So for the first place I choose an engineer, for the second a doctor and for the third a lawyer, leaving only $5$ laywers, $6$ engineers and $3$ doctors left.

For the remaining two places, I could have $2$ more people of a single profession. This is $\binom{5}{2}+\binom{6}{2}+\binom{3}{2}$ possibilities.

I could also have two people of different professions; a doctor and a laywer, $\binom{5}{1}\binom{3}{1}$; a doctor and an engineer, $\binom{6}{1}\binom{3}{1}$; or an engineer and a laywer $\binom{6}{1}\binom{5}{1}$.

This adds up to $\binom{5}{2}+\binom{6}{2}+\binom{3}{2}+\binom{5}{1}\binom{3}{1}+\binom{6}{1}\binom{3}{1}+\binom{6}{1}\binom{5}{1}=91$ possible committees.

I have two questions regarding my approach to the problem. Question $a)$ is the reasoning right, am I not overcounting? $b)$ Even if it is right, is there a simpler way to do this? You can see that the sum I end up with, though relatively simple, is quite long and tedious.

Thanks in advance!

Answer 1

I think Inclusion Exclusion is an easier approach.

If we ignore the restriction, there are $\binom {17}5$ ways to choose the group.

We then exclude the choices which miss one specified profession. That's an exclusion of $$\binom {11}5+\binom {10}5+\binom {13}5$$.

We then add back the cases in which all the people come from one profession. Thus we add back $$\binom 65+\binom 75$$

Thus the answer is $$\binom {17}5-\left(\binom {11}5+\binom {10}5+\binom {13}5\right)+\left(\binom 65+\binom 75\right)=\boxed {4214}$$

Answer 2

Let $A=\{(l,e,d)\in\{1,2,3,4,5,6\}\times\{1,2,3,4,5,6,7\}\times\{1,2,3,4\}\mid l+e+d=5\}$

Then to be found is $$\sum_{(l,e,d)\in A}\binom{6}{l}\binom{7}{e}\binom{4}{d}$$

Under the sketched conditions for equation $5=l+e+d$ we have the following possibilities:

• $5=3+1+1$
• $5=2+2+1$
• $5=2+1+2$
• $5=1+3+1$
• $5=1+2+2$
• $5=1+1+3$

This provides you a view on set $A$ and shows that the summation has $6$ terms.

Answer 3

I think it is easiest to use the principle of inclusion exclusion. Start with all $\binom{17}5$ committees, ignoring the condition that each profession must appear. Then, for each profession, subtract the bad committees where that profession does not appear. So, subtract the $\binom{13}5$ committees with no doctor, the $\binom{11}5$ committees with no lawyer, and the $\binom{10}5$ committees with no engineer. But then committees which are missing two particular professions have now been doubly subtracted, so these must be added back in to correct for this. For example, the $\binom{7}5$ committees with no doctor or lawyer.

The result is $$ \binom{17}5-\binom{13}5-\binom{11}5-\binom{10}5+ \binom{7}5 +\binom{6}5 $$

Answer 4

There are 6 types of possible committees: \begin{array} {|r|r|r|} \hline 3&1&1 \\ \hline 1&3&1 \\ \hline 1&1&3 \\ \hline 2&2&1 \\ \hline 2&1&2 \\ \hline 1&2&2 \\ \hline \end{array}

For each type of committee, it is necessary to calculate the different groups of people that compose it:

\begin{array} {|c|c|c|c|} \hline 3&1&1& {6\choose3}{7\choose1}{4\choose1}= 20\cdot7\cdot4 = 560 \\ \hline 1&3&1& {6\choose1}{7\choose3}{4\choose1}= 6\cdot35\cdot4 = 840 \\ \hline 1&1&3& {6\choose1}{7\choose1}{4\choose3}= 6\cdot7\cdot4 = 168 \\ \hline 2&2&1& {6\choose2}{7\choose2}{4\choose1}= 15\cdot21\cdot4 = 1260 \\ \hline 2&1&2& {6\choose2}{7\choose1}{4\choose2}= 15\cdot7\cdot6 = 630 \\ \hline 1&2&2& {6\choose1}{7\choose2}{4\choose2}= 6\cdot21\cdot6 = 756 \\ \hline \end{array}

Adding 6 gives a total of different committees:

$$ 560+840+168+1260+630+756 = 4214 $$

Answer 5

For groups of $6, 7$, and $4$ distinct types of members, would the counting be easier by counting all possible committees while ignoring the constraint, then subtracting the non-valid committees?

$$\binom{6 + 7 + 4}{5} - \left[ \binom{6+7}{5}+\binom{7+4}{5}+ \binom{6+4}{5} \right]$$

Non-valid committees are those which entirely omit one of the types of members.

(Ah: This doesn't work: The subtracted count is too high, as it duplicates non-valid committees. Trying again ...

$$\binom{6+7+4}{5}- \left[ \left[ \binom{6+7}{5} - \left[\binom{6}{5}+\binom{7}{5}\right] \right] + \left[ \binom{7+4}{5} - \left[\binom{7}{5}+\binom{4}{5}\right] \right] + \left[ \binom{6+4}{5} - \left[\binom{6}{5}+\binom{4}{5}\right] \right] \right] - \left[ \binom{6}{5} + \binom{7}{5} + \binom{4}{5} \right]$$

The number of committees of five members, minus the number of committees with exactly two types of members, minus the number of committees with exactly one type of member.

For two given types of members, committees with exactly two types of members are all committees of those two types of members, minus committees of only one of the types of members, minus committees of only the other type of members.

To show the complete expression, I've left the terms which evaluate to 0, and haven't simplified.