1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

Shelves

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Amrita Sep 3 '16 at 22:50
  • $\begingroup$ There are $n!$ orders, and for each order, you can do stars and bars. $\endgroup$ – AlgorithmsX Sep 3 '16 at 22:57
  • $\begingroup$ 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? $\endgroup$ – Amrita Sep 4 '16 at 1:06
  • $\begingroup$ Sort of. The main idea is that a bunch of identical objects are one specific ordering. $\endgroup$ – AlgorithmsX Sep 4 '16 at 2:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.