Assigning Committees using Probability

Date: 2/7/96 at 14:11:47
From: "Cannon Academic Center"
Subject: Probability

"If a committee of 5 people is to be chosen from 12 couples with the 
restriction that no husband and wife can be on the same committee, how 
many possible committees are there?"

I tried solving with 24 C 5/2!

Rich Hendershot               

Date: 2/14/96 at 18:0:57
From: Doctor Byron
Subject: Re: Probability

Greetings to the Cannon Academic Center.

As you probably know, if there were not the couples restriction, 
one could simply take the answer to be:

24 C 5 =

     24!
  --------
 (24-5)!*5!

giving 24*23*22*21*20/(5*4*3*2*1) = 42,504.

You can view this last series of numbers as successive choices of the
members. For the first member, you can choose from 24 possibilities,
which leaves you with 23 for the second, 22 for the third, etc.
Because we don't care about the ordering of the committee members, we
divide by 5!, the number of different ways of putting 5 members in
order.  

In the case of the couples problem, you simply eliminate two
possibilities each time a choice is made (if a wife is chosen, we also
eliminate the husband), so the solution becomes:

                                     
24*22*20*18*16   12*11*10*9*8 * 2^5       12!
-------------- = ------------------ = --------- * 2^5 = 25,344
    5!             5*4*3*2*1          (12-5)!*5!

In a more general case of a committee of n people from a group of m
couples with this restriction, the solution would be:

       m!
  ---------- * 2^n
  (m - n)!*n!

You could make this formula even more general by replacing 2 with the 
number of some other group restriction (e.g. families of 5 where only 
one member from each family can be picked).

-Doctor Byron,  The Math Forum