# "A committee of five people..." combinatorial problem

"A committee of five people is to be chosen from a club that boasts a membership of 10 men and 12 women. How many ways can the committee be formed if it is to contain at least two women, and in addition, one particular man and one particular woman who are members of the club refuse to serve together on the committee?"

This problem is provided in Richard A. Brualdi's book on Introductory Combinatorics. There are two ways to approach this (I found), however, they don't yield the same answer; and I don't know why. The first way is to consider the number of 5-member groups with the requirement that the "woman who refuses" must be a member of the group; in that case, the "man who refuses" will not be a member of the group. There are then $$\binom{11}{1}\binom{9}{3}$$ ways to form a 5-member group with exactly 2 women, $$\binom{11}{2}\binom{9}{2}$$ ways to form a 5-member group with exactly 3 women, ..., $$\binom{11}{4}$$ ways to form a 5-member groups with exactly 5 women. Then, to count the groups in with the "woman who refuses" is not a member of the group: there are $$\binom{11}{2}\binom{10}{3}$$ ways to form one with exactly 2 women, ..., $$\binom{11}{5}$$ ways to form one with exactly 5 women. If we add all those possible ways, we get: $$11\choose{1} \times 9\choose {3} + 11\choose{2} \times 9\choose {2} + 11\choose {3} \times 9\choose {1} + 11\choose {4} + 11\choose {2} \times 10\choose {3} + 11\choose {3} \times 10\choose {2} + 11\choose {4} \times 10\choose {1} + 11\choose {5} = 22506$$.

The other way we could count it is to find the total number of ways to form 5-member groups with no restriction, which would be $$\binom{22}{5}$$ and to subtract from it the number groups in which "the man who refuses" and "the woman who refuses" are required to be together. The number of 5-member groups in which both are together are then: $$\binom{11}{1}\binom{9}{2}$$, ..., $$\binom{11}{3}$$. The answer we get from $$\binom{22}{5} – \binom{11}{1}\binom{9}{2} + \binom{11}{2}\binom{9}{1} + \binom{11}{3} = 25278$$. The two results so acquired are evidently not the same. Where is the error in my reasoning?

• The number of groups with at least two women is not $\binom {22}5$.
– user
Jun 3 at 20:42
• Ahh, I see it. So then the correct computation would be $12\choose 2$$\times$$10\choose 3$$+$$12\choose 3$$\times$$10\choose 2$$+$$12\choose 4$$\times$$10\choose 1$$+$$12\choose 5$$– ($$11\choose 1$$\times$$9\choose 2 $$+$$ 11\choose 2$$\times$$9\choose 1$$+$$11\choose 3$$) = 22506$. I believe. Jun 3 at 21:17
• Formatting tip: Use $\binom{n}{k}$ to obtain $\binom{n}{k}$. Jun 3 at 22:14
• Ahh, thank you very much! Jun 5 at 1:16

There are $$\binom{22}{5}$$ ways to form the committee without constraints. From this, we must subtract the $$\binom{10}{5}$$ ways to select a committee with no women and the $$12 \binom {10}{4}$$ ways to select a committee with exactly one woman. We also must subtract the $$\binom{20}{3}$$ committees that contain the man and woman who won’t serve together.

But now we have to use the principle of inclusion and exclusion. We have overcorrected by double-counting some excluded committees. We must add back the number of committees with exactly one woman that contain both the woman and man who refuse to serve together. There are $$\binom 93$$ such committees.

$$\binom{22}{5}-\left [\binom {10}{5} + 12 \binom {10}{4}+ \binom{20}{3} \right ]+\binom 93=22506.$$

• hımm ,why didnt our answer match ? Anyway, i am going to sleep now. If you see any error in my answer, please pin me. I will check tomorrow Jun 3 at 21:31
• @NotaSalmonFish Because I had an error, now corrected. Jun 3 at 21:33

The number of all committee of five people that contain at least two women:

All situations - (there is no woman or exactly one woman) = $$\binom{22}{5}-\binom{10}{5}-\binom{10}{4}\binom{12}{1}=23562$$

The number of committees that have at least two woman also contain the situations where one particular man and woman serve together, so subtract them from the set of containing at least two woman:

The number of sets that have at least two woman and one particular woman and men serve together:

Lets assume that Bob and Alice work together (they refuse to work together). Now,we should select $$3$$ more people and at least one of these $$3$$ people must be woman ,so

All cases of $$3$$ people - no any woman: $$\binom{20}{3} -\binom{9}{3}=1056$$

Then, $$23562-1056=22506$$

• Your factor of $\binom{10}{1}$ in your first equation should be $\binom{10}{4}$. Jun 3 at 21:40
• @RobertShore silly me, thanks Jun 3 at 22:02