"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?
Best Answer
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.
Thus, our final answer is:
$$\binom{22}{5}-\left [\binom {10}{5} + 12 \binom {10}{4}+ \binom{20}{3} \right ]+\binom 93=22506.$$