2
$\begingroup$

To fulfill the requirements for a certain degree, a student can choose to take any 7 out of a list of 20 courses, with the constraint that at least 1 of 7 courses must be a statistics course. Suppose that 5 of the 20 courses are statistics courses.

From Introduction to Probability, Blitzstein, Hwang

Why is ${5 \choose 1}{19 \choose 6}$ not the correct answer?

$\endgroup$
2
  • 1
    $\begingroup$ Because you've double counted, you could choose the same two stat classes in two different ways. $\endgroup$ Mar 30, 2015 at 17:08
  • $\begingroup$ Unstated objective to find the number of ways to pick courses? Or probability that a clueless random selection of 7 courses would meet degree requirements by chance? As a start: How many ways to pick no statistics course? To pick exactly one? Etc. Have you studied the hypergeometric distribution yet? You've cheerfully accepted the answer, but altogether I wonder if you've learned anything useful from the experience of posting here. $\endgroup$
    – BruceET
    Mar 30, 2015 at 19:11

4 Answers 4

8
$\begingroup$

Because you've double counted, you could choose the same two stat classes in two different ways. If you choose stat class 1 out of five and then stat class 2 out of the remaining 19, that's going to happen again when you choose stat class 2 out of the five and stat class 1 out of the remaining 19.

$\endgroup$
4
  • 1
    $\begingroup$ how did you come up with this? When do you know that you double counted? $\endgroup$
    – bodokaiser
    Mar 30, 2015 at 17:12
  • 2
    $\begingroup$ You are picking one of the stat classes and then six of everything that remains. Suppose the stat classes are numbered S1 to S5. And suppose the others are numbered NS1 to NS15. Then the following is a legitimate list: $\{S1,S2,NS1,NS2,NS3,NS4,NS5\}$. But you counted this twice because you can get S1 from the five stat classes and then S2,NS1,NS2,NS3,NS4,NS5 from the remaining 19. Or alternatively you can get S2 from the five stat classes and S1,NS1,NS2,NS3,NS4,NS5 from the remaining 19. So you have accounted for the same list of 7 classes twice. $\endgroup$ Mar 30, 2015 at 17:34
  • $\begingroup$ So labeling the "outcomes" and trying to find conflicts should work when unsure if there is something counted twice or more. $\endgroup$
    – bodokaiser
    Mar 30, 2015 at 17:42
  • 1
    $\begingroup$ Yes, it's not a bad idea. But it might not always work if the set-up is complex with a lot of cases. But after learning how it can happen with this simple example, you should be better able to identify this issue when it comes up in other contexts. $\endgroup$ Mar 30, 2015 at 18:02
7
$\begingroup$

There are $\binom{20}{7}$ possibilities, but $\binom{15}{7}$ of them are not ok, hence the answer is $\binom{20}{7}-\binom{15}{7}$.

$\endgroup$
2
  • $\begingroup$ In R, 'x = 1:5; sum(choose(5,x)*choose(15,7-x))' returns 71,085. Also, 'choose(20,7) - choose(15,7)' gives the same answer. $\endgroup$
    – BruceET
    Mar 30, 2015 at 19:30
  • $\begingroup$ This is the correct answer, but I wish to augment the intuition based on Vandermonde's Identity. $\endgroup$ Sep 15, 2020 at 21:35
1
$\begingroup$

The animated video from the stat110x course gives a clear picture of why Vandermonde's Identity instead of $\binom{5}{1} · \binom{19}{6}$ is used.

Vandermonde's Identity:
$ \binom{m+n}{r} = \sum_{k=0}^r \binom{m}{k} \binom{n}{r-k} $

Using the video as reference for the stat class question, $\binom{m}{k}$ represents the stat classes and $\binom{n}{r-k}$ represents the none stat classes. For every stat class chosen, the number of $r$ choices reduces, hence, r-k from when choosing the none stat classes.

$ \binom{5+15}{7} - \binom{5}{0}\binom{15}{7} = \binom{20}{7} - \binom{15}{7}$

We minus $\binom{5}{0}\binom{15}{7}$ because this represents the permutations of choosing 0 stat class and 7 none stat classes.

$\endgroup$
0
$\begingroup$

The given answers are all correct. Nevertheless, there was one argument which made it very clear (to me) that $$ {5 \choose 1} {19 \choose 6} $$ is not the correct answer. It goes as follows:

Question: Suppose there are 20 different courses and five of those focus on statistics. You have to choose one "major" and six side courses. How many different combinations are possible, if the "major" must focus on statistics?

Answer: We have to choose one out of the five statistics courses and six out of the remaining 19 courses. Thus, the answer is $ {5 \choose 1} {19 \choose 6} $.

However, in the original question asked by Blitzstein, there is no reference to a "major" course. Thus, the original question (without the major course) has fewer arrangements.

$\endgroup$

You must log in to answer this question.

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