Question: We have k books to arrange on the n shelves of a bookcase. The order in which the books appear on a shelf matters, and each shelf can hold all the books. We will assume that as the books are placed on the shelves they are moved as far to the left as they will go so that all that matters is the order in which the books appear and not the actual places where the books sit. When book i is placed on a shelf, it can go between two books already there or to the left or right of all the books on that shelf.
(a) Since the books are distinct, we may think of a first, second, third, etc. book. In how many ways may we place the first book on the shelves?
(b) Once the first book has been placed, in how many ways may the second book be placed?
(c) Once the first two books have been placed, in how many ways may the third book be placed?