2
$\begingroup$

Good Day!

I was doing some combinatorics problems when I got stuck.

The problem was:

Suppose that a teacher selects 4 students from 5 boys and 4 girls. If at least one boy and one girl must be selected, then the number of distinct selecting ways is ----.

Now, I went to solve this problem like this:

We first select the minimum boys and girls needed. That would be 4 $\cdot$ 5. Now we select the rest of the 2 students which is ${7 \choose 2}$. Applying the multiplication principle, it is $20$ $\cdot$ $ 21 $ = $420$.

However, the correct answer is 120 which is done by considering the separate cases:

  • $3$ boys, $1$ girl
  • $2$ boys, $2$ girls
  • $1$ boys, $3$ girls

and then applying combinations.

What am I doing wrong?

Thanks

$\endgroup$
3
  • 3
    $\begingroup$ You are over counting. Specifically: if you choose, say, $b_1$ as the initial boy and $b_2$ as part of the second choice, that's the same as choosing $b_2$ initially and then $b_1$ as part of the second choice. $\endgroup$ Commented Apr 20, 2019 at 11:34
  • 2
    $\begingroup$ Note: another good way to do it is to compute the unrestricted number and then subtract off the all boy and all girl cases. Thus $\binom 94-\binom 54 -1 =120$ $\endgroup$ Commented Apr 20, 2019 at 11:38
  • $\begingroup$ In the first reasoning the same configuration is counted multiple times: For instance the choice: {John, Bob, Mary, Anne} is counted 4 times: as 1. {John, Mary} + {Bob,Anne}, 2. {Bob, Mary}+{John, Anne}, 3. {John, Anne} + {Bob,Mary}, 4. {Bob, Anne}+{John, Mary}. $\endgroup$ Commented Apr 20, 2019 at 11:45

3 Answers 3

Reset to default
3
$\begingroup$

You are overcounting. Consider, for example, the selection "Boy1,Girl1,Boy2,Girl2". Your formula counts it $4$ times as it counts also "Boy2,Girl2,Boy1,Girl1", "Boy2,Girl1,Boy1,Girl2", "Boy1,Girl2,Boy2,Girl1".

A possible approach here could be inclusion-exclusion:

  • number of all possible groups of $4$: $\binom{9}{4}$
  • number of all groups girls only: $\binom{5}{4}$
  • number of all groups boys only: $\binom{4}{4}$

All together $$\binom{9}{4} - \binom{5}{4} - \binom{4}{4} = 120$$

$\endgroup$
2
$\begingroup$

Consider there are 4 people : A, B, C and D. Now you want to choose 2 persons. In how many ways you can do this?

One straightforward way is ${4 \choose 2} = 6 $. So possible pairs will be AB, AC, AD, BC, BD and CD.

Another way, you first select one person and then select another person from remaining. So total there are $4 \times 3 = 12$ choices are there. But wait, there will be over counting in this method. All possible cases will be, AB, AC, AD (if first selected person is A), BA, BC, BD (if first selected person is B) and so on. So there are some pairs which are getting counted more than once.

Try to relate these two approaches to methods for that question.

$\endgroup$
1
$\begingroup$

The very first mistake you are making is when you state

We first select the minimum boys and girls needed. That would be 4 $\cdot$ 5.

If you want to count the number of two element sets with one boy and one girl, you can start off by multiplying $5$ by $4$ (order counts). Then, since order doesn't count in a set, you have to divide by $2!$. So the number of 2 element subsets with exactly one boy and one girl is $10$.

But even fixing that up you can't solve the problem attempting to use just the Rule of product and dividing by $4!$, As mentioned in a comment, you are over-counting.

When trying to count up how many elements are in a set, if you can partition the set into blocks and figure out how many elements are in each block, then mission accomplished. And to get $120$ the set is partitioned into $3$ chunks and the answer is $60 + 20 + 40$.

How about asking

How many $4$ element subsets can be created containing $2$ boys and $2$ girls?

We can now use the rule of product:

ANS: ${5 \choose 2} \times {4 \choose 2} = 60$

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.