In how many ways can $n$ unique books be arranged on $m$ shelves if at least one shelf is empty?
I am pretty sure that this is a question asking about objects and dividers, but I'm not sure how to get to the answer. There are $n!$ ways to arrange the books, and at most $m-1$ usable shelves, so would this be $n!\binom{n-1}{ m}\binom{n-1}{m}$?
Best Answer
To arrange $n$ unique books on $m$ shelves, we must insert $m - 1$ dividers among the $n$ objects. Select $m - 1$ of the $n + m - 1$ positions required for $n$ books and $m - 1$ dividers for the dividers. Then arrange the $n$ books in the remaining $n$ positions. This can be done in $$\binom{n + m - 1}{m - 1}n!$$ ways.
From these, we must subtract the number of arrangements in which every shelf is used. If every shelf is used, no two of the $m - 1$ dividers are adjacent.
To count the number of arrangements of the $n$ books in which no shelf is empty, line up the $n$ books in some order. This creates $n - 1$ spaces between successive books. To ensure that every shelf is used, we must choose $m - 1$ of these $n - 1$ spaces between books in which to place a divider, which can be done in $$n!\binom{n - 1}{m - 1}$$ ways.
Hence, the number of ways the $n$ distinct books can be arranged on $m$ shelves if at least one shelf is left empty is $$n!\binom{n + m - 1}{m - 1} - n!\binom{n - 1}{m - 1}$$
My thanks to @almagest for pointing out that if every shelf is used, the dividers cannot be placed in the first or last positions.