A High School Combinatorics Question

Question

A person picks $4$ books from the library. There are $10$ books to choose. $5$ were written by A, $3$ were written by B, and $2$ were written by C. How many combinations are there with at least one work from each author?

My initial attempt was

$5\times 3\times 2\times 7$

but it was wrong.

I assumed that the combinations possible by 1 book of each author would be

A: $5C1$

B: $3C1$

C: $2C1$

So I figured that I should multiply all the combinations with the number of books left out from the equation, hence $5\times 3\times 2\times 7$, whereas $7$ is the number of books that can be freely chosen after the picking.

Can anyone tell me where I went wrong?

There is also another question.

$9$ books are arranged on a book-shelf. $4$ of these books were written by A, $2$ by B, and $3$ by C. How many possible permutations are there if the books by C are separated from each other?

I know the solution would be

(_O_O_O_O_O_O_)

Whereas _ means the number of spaces that can be filled by book C, and O is the number of spaces that can be filled by any other book.

The answer would be $6P6\times 7P3 = 151200$

However, if I would use another method

whereas I count at least two books of C is grouped together:

then

$3 \times 2\times 8! $ should suffice right?

The answer becomes $241920$.

The total permutation of the whole thing without restrictions is $362880$

However, $362880-241920= 120960$.

Am I missing something?

Edit: I have altered the post; I'm sorry the question just now was really unclear, I missed several parts when trying to shorten the question.

Please do give me a new answer...

Answer 1

A library holds $10$ books, of which $5$ were written by A, $3$ were written by B, and $2$ were written by C. In how many ways can a person select $4$ of these books if the selection contains at least one work from each author?

For each of the three authors to be represented in a selection of four books, the person must select two books written by one of the authors and one book each written by each of the other authors. That is, the person has the following options:

• select two books written by author A, one book written by author B, and one book written by author C
• select one book written by author A, two books written by author B, and one book written by author C
• select one book written by author A, one book written by author B, and two books written by author C

$$\binom{4}{2}\binom{3}{1}\binom{2}{1} + \binom{4}{1}\binom{3}{2}\binom{2}{1} + \binom{4}{1}\binom{3}{1}\binom{2}{2}$$

You have counted each arrangement twice since there are two ways to designate a book by the author from whom two books are selected as the book written by that author. For instance, if we select books $a_1$ and $a_2$ by author A, book $b_1$ by author B, and book $c_1$ by author C, you count that selection once when you select $a_1$, $b_1$, and $c_1$ as the representatives of each author and then select $a_2$ as the additional book and once when you select $a_2$, $b_1$, and $c_1$ as the representatives of each author and $a_1$ as the additional book.

There are $9$ books on a bookshelf, of which $4$ were written by A, $2$ were written by B, and $3$ were written by C. In how many ways can the books be arranged if the books written by C are separated from each other?

Your answer $P(6, 6)P(7, 3)$ is correct.

The six books written by authors A and B can be arranged in $P(6, 6) = 6!$ ways. This creates seven spaces, five between successive books and two at the ends of the row, in which the books by author C can be placed. To ensure that the books by C are separated, we must choose three of those spaces in which to place author C's books and arrange them in those spaces, which can be done in $\binom{7}{3}3! = P(7, 3)$ ways. Hence, the number of admissible arrangements is $$6!\binom{7}{3}3! = P(6, 6)P(7, 3)$$

It is true that we could also subtract the number of arrangements in which at least two books written by author C are adjacent from the $9!$ possible arrangements of nine books. However, you counted this incorrectly.

Two books by author C are adjacent: We have eight objects to arrange: the $4$ books of author A, the $2$ books of author B, the pair of adjacent books of author C, and the other book by author C. The objects can be arranged in $8!$ ways. There are $\binom{3}{2}$ ways to select two of author C's three books to be placed adjacent to each other and $2!$ to arrange the adjacent books. This gives $$8!\binom{3}{2}2!$$ possible arrangements.

However, we have counted those arrangements in which all three of author C's books are adjacent twice, once when we designated the first two of the three books as the adjacent pair and once when we designated the second two of the three books as the adjacent pair. We only want to count such arrangements once, so we must subtract them from the total.

Three books by author C are adjacent: There are seven objects to arrange, the $4$ books by author A, the $2$ books by author B, and the block of three books by author C. The objects can be arranged in $7!$ ways. The three books can be arranged within the block in $3!$ ways. Thus, there are $$7!3!$$ such arrangements.

Therefore, the number of arrangements of the books in which at least two of author C's books are adjacent is $$8!\binom{3}{2}2! - 7!3!$$ so the number of arrangements in which no two of author C's books are adjacent is $$9! - 8!\binom{3}{2}2! + 7!3!$$

Answer 2

Each of combinations sough must include at least one book by A. In those 10 books, 5 are written by A, so there are $2^5-1$ non-empty combinations, aka subsets, of that 3-book subset (I subtracted $1$ for the empty one).
Similary, there are $2^3-1$ non-empty combinations of books by B, and each of the final combinations musct contain one of it.
And finaly there are $2^2-1$ non-empty combinations of those written by C.

Choosing any combinations from each of the above sets and combining them makes a valid combination, hence the number of valid final combinations is $$(2^5-1)(2^3-1)(2^2-1) = 31\cdot7\cdot3 = 651.$$

Answer 3

1. Every admissible choice contains two books from the same author and one book each from the remaining two authors. In your counting you have counted each choice twice: If the books $A_1$ and $A_2$ from author $A$ and books $B_1$, $C_1$ were chosen this choice is counted once as $(A_1,B_1,C_1)$ plus bonus $A_2$, and then as $(A_2,B_1,C_1)$ plus bonus $A_1$. The correct solution is $$N={5\choose2}\cdot3\cdot2+5\cdot{3\choose2}\cdot2+5\cdot3\cdot{2\choose2}=105\ .$$ 2. Your drawing is fine. There is no difference between $A$- and $B$-books. Therefore you can put these $6$ books in arbitrary order at the place of the $\bigcirc$s. This is possible in $6!$ ways. Then you can choose $3$ of the $7$ spaces for the $C$-books in ${7\choose3}$ ways and arrange the books in these spaces in $3!$ ways. It follows that there are $$6!\cdot{7\choose3}\cdot3!=151\,200$$ admissible arrangements. – Your second method of solving this problem requires more care. You have to set up a clear cut inclusion/exclusion process.