Problem with arrangement.

1. Feb 13, 2005

recon

There are 9 different books arranged neatly on a shelf. 4 of them have labels on them. In how many ways can the books be arranged such that the labelled books are separated from each other?

Here's my sorry attempt at trying to solve the problem:
There are only 12 different configurations of 'slots' into which we can put the labelled books so that they are separated. This is shown below. The slots are represented by 'x' below. The unlabelled books are represented by 'u'.

1st configuration - x,u,x,u,x,u,x,u,u
2nd configuration - u,x,u,x,u,x,u,x,u
3rd configuration - u,x,u,u,x,u,x,u,x
4th configuration - u,x,u,x,u,u,x,u,x
5th configuration - u,x,u,x,u,x,u,u,x
6rd configuration - u,u,x,u,x,u,x,u,x
7th configuration - x,u,u,x,u,x,u,x,u
8th configuration - x,u,x,u,u,x,u,x,u
9th configuration - x,u,x,u,x,u,u,x,u
10th configuration - x,u,u,u,x,u,x,u,x
11th configuration - x,u,x,u,u,u,x,u,x
12th configuration - x,u,x,u,x,u,u,u,x

So, what we need to figure out after figuring out the above is the number of ways in which the labelled books can be ordered and the number of ways in which the unlabelled books can be ordered, multiply these values together and then multiply by 12.

I know it's highly probable that the answer obtained by solving the question this way will be wrong. I also know that there's a neater way of doing it. Can anyone show me the neat way?

2. Feb 13, 2005

Galileo

It's probably neater to do the problem the other way around.
Count the number of ways to arrange the books so that the labeled books are next to each other. Then subtract that from the total number of ways to arrange the 9 books.

There are 9! ways to arrange nine books.
The 4 books next to each other can occupy their spaces in 5 positions (first to fourth, second to fifth,...,fifth to ninth).
In each of these positions you can permute the books (4! ways) to give a different (in)correct arrangement.

That's all you need to solve the problem.

3. Feb 13, 2005

recon

No, I don't think the problem can be solved that easily because none of the labelled books can be placed next to each other.

4. Feb 13, 2005

learningphysics

That's only subtracting out the ways in which all 4 books are next to each other in a row. We also need to subtract out the ways 2 are in a row, and the others arent, 3 in a row etc...

I'd solve it this way:
First arrange the other five books.
There are 5! ways to arrange them.
So consider that you've already arranged these 5 unlabelled books.

A B C D E

Now we try to place the 4 labelled books into this arrangement. We have six positions to choose from (before A, after E,in between A and B, in between B and C, in between C and D, and in between D and E). How many ways are there to place the 4 labelled books?

5. Feb 14, 2005

learningphysics

I think there are 15 configurations of the type you've done above.
x,u,u,x,u,x,u,u,x isn't there. I didn't look for the others.

6. Feb 14, 2005

recon

Hmm...there must be some logical way of getting around this. I've heard of something called the Principle of Inclusion-Exclusion. Is this applicable to the problem?

7. Feb 14, 2005

xanthym

Continuing learningphysics's enumeration:
Labeled Book (LB) #1 will have 6 possible positions to choose from. Once used, that position is no longer available, so LB #2 must select from the 5 other remaining positions. Using the same logic, LB #3 will have 4 positions to choose from, and finally LB #4 will have 3. Thus, there are {(6)x(5)x(4)x(3)} possible LB outcomes. This enumeration accounts for order, so that combined with the above result for the UNlabeled Books (i.e., (5!), the total number of possible distinct ordered arrangements is:
{Total Arrangements} = {5!}{(6)x(5)x(4)x(3)} = 43,200

~~

Last edited: Feb 14, 2005
8. Feb 14, 2005

Galileo

Sorry, didn't realize all the labeled books had to be seperated.

Learningphysics's way is nice. You could also consider the 4 labelled books (the 's):

Then, since between each 2 labelled books must be another book (a ) we have:

so there are two books left to be placed in 5 positions. Order doesn't matter so there are $\frac{(5+2-1)!}{(5-1)!2!}=15$ ways.

Permutation of the 's and 's is allowed, so the total is (15)(5!)(4!)=43200, just like xanthym's answer.

9. Feb 14, 2005

recon

Thanks a lot, all of you. I tried calculating the number of cases in which the 4 labelled books are all next to each other in one 'group'( ), the number of cases in which the labelled books are in two different 'group's ( - , - , - ) and also the number of cases in which the labelled books are in three different 'group's ( - - , - - , - - ).

However, I was unable to find any of these values as the maths was too complicated for me.

I like the methods you used in solving the problem, but it still bothers me that I cannot solve it with the method explained above.

10. Feb 14, 2005

learningphysics

Your configuration method as in your original post works. There are 15 total configurations. As you said, get the number of ways the labelled books can be ordered (4!), number of ways the unlabelled books can be ordered(5!) and multiply them all together:
15*4!*5!

I think you were very close to solving the problem. You just needed a mathematical way to calculate the number of configurations.