In how many ways can $n$ distinct books be arranged on $k$ distinct bookshelves if at least one shelf is to be empty?

Well, I tried writing out the possible number of ways for the cases that $n=1$ and $n=2$, for various $k$ values, and it looks like the answer is ${k \choose n} + k$. Is this correct? And also, what other ways are there to solve a problem like this?


Solve the problem:

  • for any arrangement of books
  • for the case when no shelf is empty

then subtract the second result from the first.

To solve the first part, represent the arrangements by strings of the form $$\text{ABC*DEFG*HIJK}\ldots$$ where $*$ represents the transition from one shelf to the shelf below.

To solve the second part, imagine that you have ordered the books in one of $n!$ ways, then choose $k-1$ of the $n-1$ apostrophes below, and replace them with asterisks: $$\mathrm{A'B'C'D'E'F'}\ldots\mathrm{'Z}$$


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.