Question

We're arranging 8 books on a shelf. How many ways can we arrange the books if the history, biology, and computer programming books (1 each) can't be together?

Answer 1

If the 3 books can't be together (but any 2 of the 3 can be) then it's 36,000 ways. If any one of the 3 books can't touch either of the other 2, it's 15,840 ways.

Explanation:

I'm not sure if the question is saying that all three books can't be together in a group (and so biology and history can be together, but biology, history and programming can't), or if the books in that group can't sit next to other books in the group (and so biology and history can't be together). Let's do it both ways - case 1 will be all three together and case 2 will be any 2 together.

Before we work this, let's first see the number of ways we can have all 8 books arranged. Order matters and so we can approach this using a permutation equation. Moreover, since we're using all the books, we'll end up with the total number being:

`8! =40,320`

Case 1 - the three books can't be together

Let's figure out the number of ways we can arrange the books and have the three be together. We can then subtract that number from the total number to get the number of ways to arrange the books without the three being together.

We can view the 3 books as 1 large book taking up 3 spaces (we'll deal with internal order in a minute). How many ways can we place the big book? It can be in slots `(1,2,3),(2,3,4),(3,4,5),...(6,7,8)=6 " ways".`

And to work out internal order of those 3 books - how many different ways can we arrange our 3 books? `3! =6`

The five remaining books can be placed in `5! =120 " ways"`

This means we have `6xx6xx120=4320 " ways"` to arrange the books having the 3 together. So the number of ways we can arrange the books without them being together is:

`40,320-4320=36,000 " ways"`

Case 2 - any 2 books can't be together

To do this one, I'm going to address the numbers of ways we can arrange the books without any 2 of the prohibited 3 touching.

Let's say for that we the three slots these books will occupy and call them `a,b,c`. To help order what is allowed and what isn't (and avoid double counting), I'm going to say:

`a < b < c`

and I'll order seats with subscripts, and so we'll have `S_n` for any given seat and `S_1` being the first seat and so on.

• `a` is constrained with `1<=n<=4`
• `b` is constrained with `3<=n<=6`
• `c` is constrained with `5<=n<=8`

And so where are the allowable spots for these three books?

With `a=1, b=3, c=5,6,7,8 =>4 " ways"`
With `a=1, b=4, c=6,7,8 =>3 " ways"`
With `a=1, b=5, c=7,8 =>2 " ways"`
With `a=1, b=6, c=8 =>1 " ways"`

And so with `a=1 => 10 " ways"`

When `a=2`, it'll push `b` and `c` out further - we lose the "4 ways" and are left with 3, 2, and 1 ways, which sums to 6.

When `a=3`, it'll push `b` and `c` out further - we lose the "3 ways" and are left with 2, and 1 ways, which sums to 3.

When `a=4`, it'll push `b` and `c` out further - we lose the "2 ways" and are left with 1 ways, which sums to 1.

All told, we have `10+6+3+2+1=22 " ways"`

The internal order of the 3 books is still `3! =6`

And the ways to arrange the remaining books is still `5! = 120 " ways"`

All told, we have `22xx6xx120=15,840`