# How many placements are there of distinct books on distinct shelves

n distinct books are placed on m distinct shelves. Two placements are considered different if they differ by a content of at least one shelf or by an order of books in a shelf. Some shelves can be empty. How many different placements are there ?

My approach: 1st book can be placed in m ways in any of the m shelves. 2nd book can be placed in again m ways.(Similar to 1st one) 3rd book can be placed in m ways .....

Answer: $n^m$ (since n books) Is this correct? I feel it is wrong because I don't think I have taken order into account for each shelf. How do I do that?

Consider the shelves going from left to right instead of top to bottom, like this:

As you can see, we can imagine putting the books in an order from left to right, then separating them out, i.e. we put books in the order $\{A,D,C,E,F,G,B,I\}$, and then we separate them out. We can separate them by using Stars and Bars. The formula for Stars and Bars is $\binom{n+m-1}{m-1}$. The total number of combinations is therefore $n!*\binom{n+m-1}{m-1}$.

• From that article that formula seems to be for n similar books into k distinct shelves. Here the books are distinct. Could you kindly elaborate more especially the last step where you multiplied by n! Thanks for using the diagram, I never thought to think of the shelves left to right – Amrita Sep 3 '16 at 22:50
• There are $n!$ orders, and for each order, you can do stars and bars. – AlgorithmsX Sep 3 '16 at 22:57
• Okay so if you order first, then for each order the books become similar and you can use the formula in that article. Is this what you mean? – Amrita Sep 4 '16 at 1:06
• Sort of. The main idea is that a bunch of identical objects are one specific ordering. – AlgorithmsX Sep 4 '16 at 2:49