Question

How many ways can n books be placed on k distinguishable shelves

a) if the books are indistinguishable copies of the same title?

b) if no two books are the same, and the positions of the books on the shelves matter?

Short answer

(a) This is\({\rm{C(k + n - 1,n)}}\), according to Theorem 2 of the book.

(b) The answer is the product of these two numbers, which may be written as\({\rm{(k + n - 1)!/(k - 1)!}}\).

Step-by-step solution

Concept Introduction

Counting is the act of determining the quantity or total number of objects in a set or a group in mathematics. To put it another way, to count is to say numbers in sequence while giving a value to an item in a group on a one-to-one basis. Objects are counted using counting numbers.

 If the books are indistinguishable copies of the same title

(a) The number of copies of the book placed on each shelf is all that matters. Let \({{\rm{x}}_{\rm{i}}}\)be the number of copies of the book placed on shelf\({\rm{i}}\), and we want to know how many solutions there are to the equation\({{\rm{x}}_{\rm{1}}}{\rm{ + }}{{\rm{x}}_{\rm{2}}}{\rm{ + }} \cdots {\rm{ + }}{{\rm{x}}_{\rm{k}}}{\rm{ = n}}\), with each \({{\rm{x}}_{\rm{i}}}\)being a non-negative integer. This is\({\rm{C(k + n - 1,n)}}\), according to Theorem 2 of the book.

If no two books are the same, and the positions of the books on the shelves matter

(b) No generality is lost if we number the books \({{\rm{b}}_{\rm{1}}}{\rm{,}}{{\rm{b}}_{\rm{2}}}{\rm{, \ldots ,}}{{\rm{b}}_{\rm{n}}}\)and think of placing book\({{\rm{b}}_{\rm{1}}}\), then placing\({{\rm{b}}_{\rm{2}}}\), and so on. There are clearly \({\rm{k}}\)ways to place\({{\rm{b}}_{\rm{1}}}\), since we can put it as the first book (for now) on any of the shelves. After \({{\rm{b}}_{\rm{1}}}\)is placed, there are \({\rm{k + 1}}\)ways to place\({{\rm{b}}_{\rm{2}}}\), since it can go to the right of \({{\rm{b}}_{\rm{1}}}\)or it can be the first book on any of the shelves. We continue in this way: there are \({\rm{k + 2}}\)ways to place \({{\rm{b}}_{\rm{3}}}\)(to the right of\({{\rm{b}}_{\rm{1}}}\), to the right of\({{\rm{b}}_{\rm{2}}}\), or as the first book on some shelf), \({\rm{k + 3}}\)ways to place\({{\rm{b}}_{\rm{4}}}\), \({\rm{ \ldots ,k + n - 1}}\)ways to place \({{\rm{b}}_{\rm{n}}}\).

As a result, the answer is the product of these two numbers, which may be written as \({\rm{(k + n - 1)!/(k - 1)!}}\).

Another, possibly simpler, way to arrive at this solution is to consider first selecting the book locations, which we did in part (a), and then selecting a permutation of the \({\rm{n}}\)books to place in those sites (shelf by shelf, from the top down, and from left to right on each shelf). As a result, the solution is \({\rm{C(k + n - 1,n)}}{\rm{.n!}}\), which is the same as the result of our previous analysis.