How many ways can six distinct black books and four distinct red books be arranged on a shelf if no two red books are adjacent?

Question

Question : There are $10$ different books on a shelf. Four of them are red and the other six are black. How many different arrangements of these books are possible if no two red books may be next to each other?

So what I have done is

1) The # of ways to range the black books $= 6!$

2) So two red books can't be placed together $= 6! \cdot \frac{7!}{3!} = 604 800$

3) I am kind of confused right now. I don't know what I should subtract $604~800$ from.

Thank you!

Answer 1

This is a perfect problem to solve with stars and bars.

We have to place 6 black books in total. We can treat the red books as "dividers", and if we do that, the problem becomes how many ways are there to rearrange (*'s are black books, |'s are red)

******||||

However, to enforce that no two red books touch, we have to place 1 book in between 3 of the dividers. So, we only have 3 black books that we have to place

***||||

So, our answer, if the books are indistinguishable, is $${7\choose3}=\color{red}{35}$$

Now, as you note, the books are different. So, we multiply by the number of arrangements of red books and black books.

So, our final answer is $$35\cdot6!\cdot4!=\color{red}{604,800}$$

Answer 2

Your answer is correct.

Let's justify your argument:

Method 1: The six black books can be arranged in a row in $6!$ ways. This creates seven spaces in which a red book can be placed, five between successive black books and two at the ends of the row.
$$\square B \square B \square B \square B \square B \square B \square$$ To ensure that no two of the four red books are adjacent, we must choose four of these spaces in which to place a red book, which can be done in $\binom{7}{4}$ ways. The four red books can be arranged in these spaces in $4!$ ways. Hence, the number of admissible arrangements is $$6!\binom{7}{4}4! = 6! \cdot \frac{7!}{3!} = 604800$$ as you found. There is no need to subtract.

Let's confirm your result. The following argument is more formal. Alas, it is also trickier, particularly when we count those arrangements in which there are two disjoint pairs of adjacent books.

Method 2: We use the Inclusion-Exclusion Principle.

Since there are $10$ different books on the shelf, they can be arranged in $10!$ ways. From these, we must subtract those arrangements in which a pair of red books are adjacent.

A pair of adjacent red books: A pair of adjacent red books can be selected in $\binom{4}{2}$ ways. We now have nine objects to arrange, the six black books, the pair of adjacent red books, and the other two red books. The objects can be arranged in $9!$ ways. The pair of adjacent books can be arranged internally in $2!$ ways. Hence, there are $$\binom{4}{2}9!2!$$ arrangements with a pair of adjacent red books.

However, if we subtract the number of arrangements with a pair of red books from the total, we will have subtracted too much since we will have subtracted each arrangement with two pairs of adjacent red books twice, once for each way of designating one of the pairs as the pair of adjacent red books. Thus, we add those arrangements to the total.

Two pairs of adjacent red books: This can occur in two ways. Either the pairs are disjoint or overlapping, meaning that there are three consecutive red books.

Two disjoint pairs of adjacent red books: Since the red books are distinct, there must be some ways of distinguishing them. Say they have different titles. If so, then there are three ways to pair one of the other red books with the one whose title appears first in an alphabetical list. The other two red books must form the other pair of adjacent red books. We have eight objects to arrange, the six black books and two disjoint pairs of red books. The objects can be arranged in $8!$ ways. Each pair of adjacent red books can be arranged internally in $2!$ ways. Hence, there are $$\binom{3}{1}8!2!2!$$ arrangements with two disjoint pairs of red books.

Two overlapping pairs of adjacent red books: The three consecutive red books can be selected in $\binom{4}{3}$ ways. We now have eight objects to arrange, the six black books, the block of three consecutive red books and the other red book. The objects can be arranged in $8!$ orders. The trio of consecutive red books can be arranged internally in $3!$ ways. Hence, there are $$\binom{4}{3}8!3!$$ arrangements with two overlapping pairs of red books.

Hence, there are $$\binom{3}{1}8!2!2! + \binom{4}{3}8!3!$$ arrangements with two pairs of adjacent red books.

However, if we subtract the number of arrangements with a pair of adjacent red books and then add the number of arrangements with two pairs of adjacent red books from the total, we fail to exclude those arrangements with three pairs of adjacent red books, which can only occur if there are four consecutive red books since there are only four red books. The reason is that we subtracted such arrangements three times, once for each way of designating one of the three pairs of adjacent red books as the pair of adjacent red books, and added them three times, once for each of the $\binom{3}{2}$ ways of designating two of the three pairs of adjacent red books as the two pairs of adjacent red books.

Three pairs of adjacent books: There are seven objects to arrange, the six black books and the block of four red books. The objects can be arranged in $7!$ ways. The block of four red books can be arranged internally in $4!$ ways. Hence, there are $$7!4!$$ arrangements with three pairs of adjacent red books.

Hence, the number of arrangements of six distinct black books and four distinct red books in which no two red books are adjacent is $$10! - \binom{4}{2}9!2! + \binom{3}{1}8!2!2! + \binom{4}{3}8!3! - 7!4! = 604800$$ as you found.