0
$\begingroup$

A committee of 6 is being formed from a group of 12 sophomores and 10 freshmen. How many committees can be formed if at least 3 have to be sophomores?

I know one way is to split this into cases of including 3, 4, 5, and 6 sophomores and then add all the cases, but I tried to do it another way:

Since at least three sophomores have to be included, first choose 3 sophomores from the 12. Once that is done, you are left with 9 sophomores + 10 freshmen, out of which you need to choose three more. This gives the expression $\binom{12}{3} \binom{19}{3}$.

However, this is incorrect but I cannot figure out why.

$\endgroup$
5
  • $\begingroup$ Hint: What happens when you have 4 sophomors? $\endgroup$ Commented Apr 2, 2014 at 1:22
  • $\begingroup$ @GrahamKemp I don't understand -- isn't the four sophomore case still covered by $\binom{12}{3} \binom{19}{3}$? $\endgroup$
    – 1110101001
    Commented Apr 2, 2014 at 1:24
  • $\begingroup$ yes, but how many times is each combination counted? $\endgroup$ Commented Apr 2, 2014 at 1:27
  • $\begingroup$ Accidental duplicate, see answers math.stackexchange.com/questions/714537/… ignore typo in question title. $\endgroup$
    – Alec Teal
    Commented Apr 2, 2014 at 1:30
  • $\begingroup$ @GrahamKemp The four sophomore case is counted $\binom{4}{3}$ times, right? And the five sophomore case is counted $\binom{5}{3}$ times each? $\endgroup$
    – 1110101001
    Commented Apr 2, 2014 at 1:32

3 Answers 3

2
$\begingroup$

It's the sum of all the ways to select an exact number of sophomors, and the remainder in freshmen, when the number is from 3 to 6.

$$\sum_{k=3}^6 {12 \choose k}{10-k\choose 6-k}$$


It has to be done this way to avoid multiple counting of identical sequences.

Let us examine a simpler case to demonstrate.

Say we have sophomores $\{A,B,C\}$ and freshment $\{d, e\}$, who are to form a team of 4 with at least 2 sophomores.

By your method we would count: ${3 \choose 2}{3 \choose 2}= 12$

This is counted by the ${3\choose 2}$ ways to pick 2 sophomores: $\{A, B\}, \{A, C\}, \{B, C\}$ and for each ${3\choose 2}$ ways to pick the remainder of the team: $\{X, d\}, \{X, e\}, \{e, f\}$ where $X$ is the unpicked sophomore. So the total combinations are: $$\color{blue}{\{A, B, C, d\}, \{A, B, C, e\}}, \{A, B, e, f\}, \\ \color{red}{\{A, C, B, d\}, \{A, C, B, e\}}, \{A, C, e, f\}, \\ \color{red}{\{B, C, A, d\}, \{B, C, A, e\}}, \{B, C, e, f\}$$

But look, we have duplicates. We've over-counted when there are three sophomores on the team. (It would be a different case if the first picked sophomores were given leadership, but when they're simply team members, the order of picking doesn't matter).

So the proper approach is to count the ways to form teams with exactly 2 and with exactly 3 sophomores. ${3 \choose 2}{2\choose 2}+{3 \choose 3}{2\choose 1} = 3+2 = 5$

$\endgroup$
3
  • $\begingroup$ Yes, I know that is one way to do it -- I am looking for an explanation as to why my proposed method to solve it does not work. $\endgroup$
    – 1110101001
    Commented Apr 2, 2014 at 1:26
  • $\begingroup$ And I think the expression you gave is incorrect. It should be: $\sum _{k=3}^6 \binom{12}{k} \binom{10}{6-k}$ $\endgroup$
    – 1110101001
    Commented Apr 2, 2014 at 1:28
  • $\begingroup$ Your proposed method does not work because it counts certain combinations multiple times. $\endgroup$ Commented Apr 2, 2014 at 1:35
1
$\begingroup$

The expression ${12\choose3}{19\choose3}$ would be correct if you were counting the number of ways to form a committe with three leaders who all had to be sophomores. As such, it counts leaderless committees with more than three sophomores multiple times.

$\endgroup$
0
$\begingroup$

The split cases approach makes sense since they ask for "at least 3"

If you wanted to do it another way, you could say:

$$\,^{22}C_6 - \,^{12}C_2 \cdot \,^{10}C_4 - \,^{12}C_1 \cdot \,^{10}C_5 - \,^{12}C_0 \cdot \,^{10}C_6$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .