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}$.