In how many ways n different books be arranged such that no two particular books are never together?

Question

permutations

Answer 1

There are n! ways to arrange the n books. But you need to subtract the invalid arrangements, where two books (say A and B) are together.

So how many ways are there to place A and B together within n books?

For example if there were 8 books, there are 14 ways.
ABxxxxxx
xABxxxxx
xxABxxxx
xxxABxxx
xxxxABxx
xxxxxABx
xxxxxxAB
BAxxxxxx
xBAxxxxx
xxBAxxxx
xxxBAxxx
xxxxBAxx
xxxxxBAx
xxxxxxBA

You can see that there are (n-1) ways to pick the first book (A) and then the second book is after. But the books can be reversed. So, in general there are (n-1) * 2 ways to arrange two books together. Then you need to arrange the remaining n-2 books around them in (n-2)! ways. So there are 2(n-1) * (n-2)! "bad" arrangements. Notice how (n-1) * (n-2)! = (n-1)!, so you can simplify this to 2(n-1)!

So the final answer is:
n! - 2(n-1)!

Answer 2

In general, there are n! ways to arrange n books.

You start with that amount, and then deduct arrangements in which the two books are together.

The books could be in positions 1 and 2, then 2 and 3, 3 and 4, and so on. That's n-1 possibilities, but then you double it, because the books can be in either order. So now you have 2(n-1).

The other n-2 books can be arranged in any order around these two, so you multiply this amount by (n-2)!, for a total of 2(n-1)(n-2)!, which simplifies to 2(n-1)!.

This is the total number of permutations in which the 2 books are next to each other. Deduct these from the original n! and you have the total number of permutations.