2
$\begingroup$

Given $m \ge n \ge 1$, how many ways are there to place m books on n shelves, such that there is at least one book on each shelf?

Placing the books on the shelves means that:
• we specify for each book the shelf on which this book is placed, and
• we specify for each shelf the order (left most, right most, or between other books) of the books that are placed on that shelf.

I solve this problem in the following way:

If $m=n$, there are $m!$ or $n!$ ways to do it
Else:

  1. Place $n$ books on $n$ shelves: $n!$ ways to do it
  2. Call the set of $m-n$ remaining books $T=\{t_1, t_2,..,t_{m-n}\}$
    The procedure for placing books on shelves: choose a shelf, choose a position on the shelf
    We know choosing a shelf then place the book on the far left has $n$ ways
    For book $t_1$, there is a maximum of $1$ additional position (the far right). Thus there is $n+1$ ways to place book $t1$.
    For book $t2$, there is a maximum of $2$ additional positions. Thus there is $n+2$ ways for book $t_2$
    ...
    For book $t_i$, there is a maximum of $i$ additional positions. Thus there is $n+i$ ways for book $t_i$
    In placing $m-n$ books, we have $(n+1)(n+2)...(n+m-n)$ or $(n+1)(n+2)..m$ ways
    In total, we have $n!(n+1)(n+2)...m$ or $m!$ ways

Is there any better solution to this problem?

$\endgroup$
  • $\begingroup$ "Given $n\geq m\geq 1$, how many ways are there to place $m$ books on $n$ shelves such that there is at least one book on each shelf"... So... there are more shelves than books or at least as many shelves as books? Are you sure you don't mean to have $m\geq n\geq 1$? If it really were $n\geq m\geq 1$ then the answer is zero for all situations where $n>m$ and $m!$ for all situations where $n=m$ $\endgroup$ – JMoravitz Apr 24 '17 at 20:17
  • 2
    $\begingroup$ With the correction $m\geq n\geq 1$, the answer is not $m!$, but is rather $m!\binom{m-1}{n-1}$. Consider arranging the books in a single row first, then picking $n-1$ different spaces between the books in which you'll place dividers, these dividers representing where one shelf will end and the next shelf begins. $\endgroup$ – JMoravitz Apr 24 '17 at 20:18
  • $\begingroup$ When a book desires to remain alone on its shelf, it's pure shelfishness. $\endgroup$ – Jean Marie Apr 24 '17 at 21:00
3
$\begingroup$

Given that the ordering of the books is important, not merely which shelf they are on, you can simply split any book ordering into shelves by choosing the $n{-}1$ shelf breaks from the $m{-}1$ book gaps. So there are

$$m!\binom{m-1}{n-1} = \frac{m!(m-1)!}{(m-n)!(n-1)!} \text{ options}$$

$\endgroup$

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.