# Combinatorics problem, right solution?

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.

• I corrected it, I apologize. The result is the same though, it was just a typo. – Lafinur Apr 25 at 15:45
• That number seems far too small. If you ignore the restriction there are $\binom {17}5=6188$ possible combinations. – lulu Apr 25 at 15:51
• When you say, for example, "pick a lawyer and then later possibly pick more lawyers", you're guaranteed to introduce an overcount. You might pick LawyerA first and then LawyerB or you might pick LawyerB first and then LawyerA. These are precisely the same subset of lawyers, but your counting scheme considers them to be different. – Austin Mohr Apr 25 at 17:48
• To explain why your answer is so small... "For the first place I choose an engineer" okay, and how many options were there for which engineer takes this spot? How does this affect the total count? Similarly so for the other professions. This would give an answer of $6\times 7\times 4\times 91 = 15288$ which as explained in previous comment is indeed overcounting. This however would be the answer to the question of how many five person teams we can make which have a designated "lead engineer" and "lead lawyer" and "lead doctor" on the team. – JMoravitz Apr 25 at 18:52
• Note also that $\binom{5}{2}+\binom{6}{2}+\dots=91$ is simply $\binom{14}{2}$, the number of ways of choosing two more people from the $(6-1)+(7-1)+(4-1)=14$ people remaining after having selected a lead lawyer, lead engineer, and lead doctor to fill out the rest of the team. – JMoravitz Apr 25 at 18:54

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}$$

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$$

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.

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$$

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.