# Faulty Combinatorial Reasoning?

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?

-
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

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$.
-

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.

-

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.

-

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.

-