Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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. –  EuYu Nov 6 '12 at 4:15

2 Answers 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 4}$ 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}$

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.