3
$\begingroup$

The first part of the question I know how to answer:

How many committees of five men and four women can be formed from and organization with 43 women and 47 men?

The answer to this of course would be $C(47,5)\cdot C(43,4)=\frac{47!43!}{42!39!5!4!}$

The second part of the problem I'm having difficulty with:

Suppose in the previous scenario that among the members there are 20 married couples and there is a rule prohibiting spouses from serving on the same committee. How many five-man, four-woman committees can be formed under this new restriction?

My intuition tells me that there could at most be 4 married couples on the same committee with one extra man under the first part of the problem and I should be able to subtract all the cases with 4 couples, 3 couples, 2 couples and 1 couple on a committee. I'm not sure how I should write that mathematically since I'm uncertain if I'm choosing out of the 20 couples at that point or out of the entire group of people.

  • 1
    It's not as straightforward to choose exactly $4$ couples, or exactly $3$ couples and so on. The simplest would probably to use inclusion-exclusion.2012-11-06

2 Answers 2

2

Neither approach is really simple. I would follow yours: if there are three married men, you have ${20 \choose 3}$ ways to choose those men, ${27\choose 2}$ ways to choose the others, and ${40 \choose 1}$ ways to choose the women. So letting $i$ be the number of men from couples you have $\sum_{i=0}^4 {20 \choose i}{27 \choose 5-i}{43-i \choose 4-i}.$ 

2

Suppose the number of coupled women on the committee is $k$. These can be chosen in $\binom{20}{k}$ ways. For every one of these ways, the number of non-coupled women is $4-k$, and these can be chosen in $\binom{23}{4-k}$ ways. Now the $5$ men can be chosen from the $47-k$ eligible in $\binom{47-k}{5}$ ways, for a total of $\binom{20}{k}\binom{23}{4-k}\binom{47-k}{5}$ ways.

Add up, $k=0$ to $k=4$.

Remark: Doing it by counting the number of illegal committees is possible, but I think one cannot avoid the division into several cases. And several of the cases are somewhat more complicated than with the direct approach.