9
$\begingroup$

Problem: A club has 5 men and 7 women. How many ways are there to choose 4 people such that at least one man and woman are chosen?

The correct answer is 455 and can be obtained by

$${12 \choose 4} - {5 \choose 4} - {7 \choose 4}.$$

However, I am unsure of the flaw in the following reasoning below which leads to an answer of 1575:

$${5 \choose 1}{7 \choose 1}{10 \choose 2}.$$

This quantity ensures that a man and woman are chosen, and then we select two of the remaining 10 people. As a result, we have chosen 4 people, of which there are at least 1 man and 1 woman.

$\endgroup$
1
  • 1
    $\begingroup$ The former method gives $455$ when I calculate it. $\endgroup$ – jl00 Oct 9 '19 at 2:18
10
$\begingroup$

The second answer counts a slightly different problem where we not only choose a group including at least one man and one woman, but within that group, we choose a man and a woman - which gives an answer that is too high because we are making choices beyond what we were supposed to count.

Suppose, for instance, that we name the men $M_1,\ldots,M_5$ and the women $W_1,\ldots,W_7$. Your answer considers the following sequences of choices as distinct:

We choose $M_1$ then $W_1$ and then add $M_2$ and $W_2$.

We choose $M_1$ then $W_2$ and then add $M_2$ and $W_1$.

We choose $M_2$ then $W_1$ and then add $M_1$ and $W_2$.

We choose $M_2$ then $W_2$ and then add $M_1$ and $W_1$.

In the end, we end up with the same group from each sequence of choices - but you've counted the number of ways to make these choices in sequence when, in reality, several sequences can lead to the same result. Note that this can't be fixed by dividing by $4$ because, if we chose a group of one man and three women, there would only be $3$ ways to reach that group - indeed, your answer is somewhat more than $3$ times the correct answer because of this over-counting.

The suggested answer instead takes all the ways to create a group of $4$, then subtracts out those that include only a single gender - which properly counts "groups of $4$" rather than "sequences of choices".

$\endgroup$
3
$\begingroup$

Hint: Suppose the men are selected from $\{\text{Adam, Bob, Carl, Dennis, Edgar}\}$ and the women from $\{\text{Alice, Barbara, Chloe, Darcy, Emily, Fiora, Gertrude}\}$.

We choose one man, say $\text{Bob}$ and one woman, say $\text{Alice}$. Then we choose two from ten that are neither of the already selected, say $\text{Emily}$ and $\text{Fiora}$.

Now for another group, choose one man, say $\text{Bob}$ once again. Then choose a woman, say $\text{Emily}.$ Now choose two out of the remaining ten, $\text{Alice} $ and $\text{Fiora}$.

Notice we've double counted the group of $\text{Alice, Bob, Emily, Fiora}$, using the latter method.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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