# 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?

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}$.
• There are $n!$ orders, and for each order, you can do stars and bars. – AlgorithmsX Sep 3 '16 at 22:57