# Counting: A committee made of men and women (GRE question)

In how many ways can a committee of $5$ members be formed from $4$ women and $6$ men such that at least $1$ woman is a member of the committee.

I know that the correct answer is:

$\binom{10}{5} - \binom{6}{5} = 246$

In hindsight (after reading the solution guide), that all makes sense (All Groups - Just those with $5$ Men). However, I can't figure out why my original solution doesn't work. I would choose $1$ of the women, and then choose any $4$ from the remaining $9$ people. This gives us:

$\binom{4}{1}\binom{9}{4} = 504$

Can anyone explain why that doesn't work? Thank you for your help!

• Double counting. You count the case Alice, Betty, Charles, David, Edward twice, once when Alice is the first woman chosen, and once when Betty is. – saulspatz Jul 1 '18 at 15:55
• What is GRE question? – Aqua Jul 1 '18 at 15:56
• @Angle Graduate Record Exam. Used for admission to graduate school in the United States. – saulspatz Jul 1 '18 at 15:58
• The amount $\binom{4}{1}\cdot \binom{9}{4}$ counts the number of ways in which you can form a 5 member committee from 4 women and 6 men where one member of the committee is designated as the leader and is distinguishable from the other members of the committee subject to the constraint that that leader must be female. In effect, by having used multiplication principle in the manner you attempted, you are designating the woman chosen in the first step as being distinguishable from any potential women chosen in the second step which should not have been done. – JMoravitz Jul 1 '18 at 16:42

Your solution counts twice the configuration with two women, three times the configurations with $3$ women, etc.

Imagine that the question was to form a committee with four women. Your solution would yield "choose one woman (4 options) and then there are ${3\choose 3}=1$ way to choose the remaining three, so four ways altogether (where the answer is obviously $1$: take all four women).

\begin{array}{c|c|c|c|c|c|c} 4 \mbox{ Women}&6\mbox{ Men}&\mbox{Number of Selections}\\\hline 1&4&^4C_1\times^6C_4=60\\ 2&3&^4C_2\times^6C_3=120\\ 3&2&^4C_3\times^6C_2=60\\ 4&1&^4C_4\times^6C_1=6\\ \ \\ \end{array} Now the total number of ways of forming a committee of $5$ members with at least $1$ women is $60+120+60+6=246$ ways.

If you want to use that method it would be: $$^9C_4 + ^8C_4 + ^7C_4 + ^6C_4 = 246$$

Otherwise you are double counting.

The number of groups with exactly $k$ of the four women and $5 - k$ of the six men is $$\binom{4}{k}\binom{6}{5 - k}$$ so the number of groups with exactly $k$ women is \begin{align*} \sum_{k = 1}{4} \binom{4}{k}\binom{6}{5 - k} & = \binom{4}{1}\binom{6}{4} + \binom{4}{2}\binom{6}{3} + \binom{4}{3}\binom{6}{2} + \binom{4}{4}\binom{6}{1}\\ & = 4 \cdot 15 + 6 \cdot 20 + 4 \cdot 15 + 1 \cdot 6\\ & = 60 + 120 + 60 + 6\\ & = 246 \end{align*} as you found more easily by subtracting the number of groups of five people with no women from the number of groups of five people that can be formed without restriction.

Suppose the women are Angela, Brenda, Charlotte, and Denise and that the men are Edward, Frank, George, Henry, Ivan, and Jeffrey. By designating a particular woman as the representative of the women in the group, you count each group the number of times as the number of women in the group. For instance, consider the group consisting of the four women and Edward. You count it in each of the following ways:

\begin{array}{c c} \text{designated woman} & \text{additional members of the group}\\ \hline \text{Angela} & \text{Brenda, Charlotte, Denise, Edward}\\ \text{Brenda} & \text{Angela, Charlotte, Denise, Edward}\\ \text{Charlotte} & \text{Angela, Brenda, Denise, Edward}\\ \text{Denise} & \text{Angela, Brenda, Charlotte, Edward} \end{array}

Notice that $$\color{red}{\binom{1}{1}}\binom{4}{1}\binom{6}{4} + \color{red}{\binom{2}{1}}\binom{4}{2}\binom{6}{3} + \color{red}{\binom{3}{1}}\binom{4}{3}\binom{6}{2} + \color{red}{\binom{4}{1}}\binom{4}{4}\binom{6}{1} = 504$$ where the factor $\color{red}{\binom{k}{1}}$ is the number of ways of designating one of the $k$ women in the group as the representative of the women in the group.