# Combinatorics - How many committees are possible in this case

Consider the following question:

A committee of $4$ is to be chosen from $7$ people. $2$ of the $7$ people cannot work together. How many committees are possible if the two do not work together.

Here is how I am solving it

Total No. of possibilities = With Enemies + Without Enemies

Total No. of possibilities = $\tbinom{7}{4} = 35$

With Enemies (I considered the workers who are enemies as a single unit) = $\tbinom{6}{4} = 15$

Now I am getting $35-15 = 20$ which is wrong, I was suppose to get $25$. Could anyone tell me where I am going wrong ?

-
Think about the logic behind 6-choose-4. Are there really 6 items to choose from? Are you really choosing 4 items? – Gerry Myerson Aug 16 '12 at 12:50

You went astray in counting the number of unacceptable committees. To form an unacceptable committee, you must first choose the two enemies and then fill out the rest of the committee with any $2$ of the remaining $5$ people, so there are $\binom52=10$ unacceptable committees. Your final result will then be $35-10=25$, which is correct.

You can also calculate the number of acceptable committees directly. There are $\binom54=5$ committees that can be formed without including either of enemies. If you include one of the enemies, there are $2$ ways to choose which one to include and then $\binom53$ ways to choose the other $3$ committee members, for a total of $\binom54+2\binom53=2\cdot10=5+20=25$ possible committees.

Added: When you group the enemies as one entity and then choose $4$ of the resulting $6$, you’re making two mistakes. First, those $\binom64=15$ foursomes include the $\binom54$ committees that can be chosen from the $5$ non-enemies. Secondly, if the enemy pair is one of the $4$ that you choose, you’re also choosing three more people, so you’re making a $5$-person committee.

-
You stated "To form an unacceptable committee, you must first choose the two enemies and then fill out the rest of the committee with any 2 of the remaining 5 people, so there are $_5C_2$ unacceptable committees." Could you explain this a bit more I still don't get it. How did you get 5 and how did you get 2 ? – MistyD Aug 16 '12 at 12:56
Another hint trampled by an answer. – Gerry Myerson Aug 16 '12 at 12:57
Misty, how did you get 6, and how did you get 4? – Gerry Myerson Aug 16 '12 at 12:58
@GerryMyerson To get 6 , I grouped the two enemies as one so 7-1 = 6 and 4 was the committee requirement. – MistyD Aug 16 '12 at 12:59
@Misty: After you’ve put the two enemies on your committee (which is the only way to make it unacceptable), you still need $2$ more members. There are $7-2=5$ people left who aren’t yet on your committee, so you must choose $2$ of these $5$. You can do this in $\binom52$ ways. – Brian M. Scott Aug 16 '12 at 12:59

Suppose the seven people are A,B,C,D,E AND F and A and B are enemies. Ways in which acceptable communities can be formed are:

i. Including A and any 3 of the other 5 people, excluding B.

ii. Including B and any 3 of the other 5 people, excluding A.

iii. Excluding both A and B.

Number of ways in which i can be done = $\tbinom{5}{3}$ = 10

Number of ways in which ii can be done = $\tbinom{5}{3}$ = 10

Number of ways in which iii can be done = $\tbinom{5}{4}$ = 5

So, total possible ways = 25.

-