Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have 10 books, 4 of which are biographies while the remaining 6 are novels. Suppose I have to choose 4 total books with AT LEAST 2 of the 4 books being biographies. How many different combinations of choosing 4 books in such a way are there?

The following line of reasoning is faulty, but I can't figure out why:

First we figure out how many ways there are of choosing 2 biographies from 4. Then we multiply this by the number of ways there are of choosing 2 of any of the remaining books from 8. This way we will ensure that we get at least two biographies (perhaps more) when we enumerate the choices. Then we have:

  1. BIOGRAPHIES: There are (4*3)/2! choices for the two biographies (we divide by 2! since the order in which the two biographies are chosen doesn't matter).
  2. REMAINING BOOKS: There are now 8 books left (6 novels, 2 biographies), which can be chosen in any order. This leaves us with (8*7)/2! choices.
  3. Overall we have [(4*3)/2!]*[(8*7)/2!] = 168 total choices.

Where did I go wrong?

share|improve this question
    
How could I adjust for the over-counting I did here? (Rather than constructing the answer of 115 by adding together the discrete cases of choosing 2 bios, 3 bios, and 4 bios)? –  George Sep 4 '12 at 22:15

4 Answers 4

In your reasoning, you are counting some cases several times. For example, if you take the biographies $B_1$ and $B_2$ as your mandatory biographies and take $B_3$ and $B_4$ as the two other ones, or if you take $B_£$ and $B_4$ as the mandatory ones and $B_1$ and $B_2$ as the other books, it is the same choice of $4$ books, but it will be counted twice.

To solve the problem:

  1. the number of ways of choosing $4$ books is $A_4 = \frac{10!}{4!\times6!} = 210$
  2. the number of ways of choosing $4$ books with no biographies is $B_0 = \frac{6!}{4!\times2!} = 15$
  3. the number of ways of choosing $4$ books with exactly $1$ biographies is $B_1 = 4\times\frac{6!}{3!\times3!} = 80$ (you pick $1$ biography amongst $4$ and then choose $3$ novels).
  4. the number of ways of choosing at least two biographies is $B_2^+ = A_4 - (B_1+B_2) = 115$.
share|improve this answer

Your enumeration would count the following possibilities (and many other similar examples) separately:

  1. First choose Bio1 and Bio2, then choose Bio3 and Novel1.
  2. First choose Bio1 and Bio3, then choose Bio2 and Novel1.

Notice the only difference is that I switched when Bio2 and Bio3 would be chosen.

In general, it is best to split "at least"-type questions into several instances of "exactly". Here, you should try to count the ways to get exactly two, exactly three, and exactly 4 biographies as separate problems, then add up all the cases.

share|improve this answer

When you do this you sum two times the cases when you have more than two biographies books. Then need to do this

2 BIOGRAPHIES books: $\dfrac{4\cdot3}{2!} \cdot \dfrac{6\cdot5}{2!}=90 $

3 BIOGRAPHIES books: $\dfrac{4\cdot 3 \cdot 2}{32!} \cdot 6 =24$

4 BIOGRAPHIES books: 1

then the result is 115.

share|improve this answer

Suppose the biographies are of $A$, $B$, $C$, and $D$. Among the ways you counted when initially you chose two biographies, there were the biographies of $A$ and of $B$. Among the choices you counted when you chose two more books was the biography of $C$ and novel $N$. So among the choices counted in your product was choosing $A$ and $B$, then choosing $C$ and $N$. That made a contribution of $1$ to your $168$.

But among the choices you counted when you chose two biographies, there were the biographies of $A$ and $C$. And among your "two more" choices, there was the biography of $B$ and novel $N$. So among the choices counted in your product, there was the choice of $A$ and $C$, and then of $B$ and $N$. That made another contribution of $1$ to your $168$.

Both of these ways of choosing end us up with $A$, $B$, $C$, and $N$. So does choosing $B$ and $C$ on the initial choice, and $A$ and $N$ on the next. Still another contribution of $1$ to your $168$.

So your product counts the set $\{A, B, C, N\}$ three times. This it does for every combination of three biographies and one novel. It also overcounts the set $\{A, B, C, D\}$.

One could adjust for the overcount. In some problems that is a useful strategy. Here it takes some care.

But a simple way to solve the problem is to count separately the ways to choose two bios, two novels; three bios, one novel; four bios, no novels and add up.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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