\problemdata     
{S01-PS7-5}           
{counting, combinations}              
{} 		
{S98-PS7, S01-PS7}
{S01 Karger}



        
\begin{problem}


Six women and nine men are on the faculty of a school's
EECS department.  The individuals are distinguishable.
How many ways are there to select a committee of 5
members if at least 1 woman must be on the committee?

\solution{
        
\textbf{First method: (by brute force)}We need to count all possible combinations of people such that there
is at least one woman in every combination, but we must remember not
to count any combinations multiple times.  

We can have committees with 

1 woman, 4 men: $ { 6 \choose 1} {9 \choose 4}$\\
2 women, 3 men: $ { 6 \choose 2} {9 \choose 3}$\\
3 women, 2 men: $ { 6 \choose 3} {9 \choose 2}$\\
4 women, 1 man: $ { 6 \choose 4} {9 \choose 1}$\\
5 women, 0 men: $ { 6 \choose 5} {9 \choose 0}$\\

So there are 
$ { 6 \choose 1} {9 \choose 4} 
+ { 6 \choose 2} {9 \choose 3}
+ { 6 \choose 3} {9 \choose 2}
+ { 6 \choose 4} {9 \choose 1}
+ { 6 \choose 5} {9 \choose 0} = 2877$ different possibilities for
committees.

\medskip

\textbf{Second method:}
Another way to solve this problem is to say that there are ${15 \choose 5}$
different committees, and ${9 \choose 5}$ committees of just men.  So there
are ${15 \choose 5} - {9 \choose 5}= 2877$ different possibilities for committees. 


Note that $6 \cdot { 14 \choose 4} =6006$ is not a correct answer.  
The product rule
only applies when you are choosing two separate sets of items which are
independent of each other.  
In this case, a
woman is chosen and then the remainder of the committee is chosen, but since
there may be women in the last set of $4$ chosen, we will be double counting.
For example, if $A$ and $B$ are women, and $C, D, $ and $E$ are men, then
we will count $A$, \{$BCDE$\} as well as $B$, \{$ACDE$\}.  
}                    

\end{problem}