From Discrete and Combinatorial Mathematics: An Applied Introduction:
Pamela has 15 different books. In how many ways can she place her books on two selves so that there is at least one book on each shelf? (Consider the books in each arrangement to be stacked one next to the other, with the first book on each shelf at the left of the shelf.)
Initially, I thought that this would be fairly straight forward. There are two cases where either shelf could be empty and so we would subtract 2 from the total number of permutations which is obviously $15!$. It is obvious now that both of these statements are false.
My previous thoughts didn't take into account the fact that there are two shelves and that the books could be stacked in such a way that 5 are on the top shelf and 10 are on the bottom, or 8 on top with 7 on bottom, or any number of other ways. I believe there are $2^{14}$ ways the books can be distributed amongst the two shelves (keep in mind that each shelf has to have at least one book, $15 – 1 = 14$) if the ordering of the books didn't matter, but it does. Is this correct?
My book also talks about the rule of product:
If a procedure can be broken down into first and second stages, and if there are $m$ possible outcomes for the first stage and if, for each of these outcomes, there are $n$ possible outcomes for the second stage, then the total procedure can be carried out, in designated order, in $mn$ ways.
If we consider that the top shelf represents the first "stage" and the bottom represents the second and that $b_{top}$ represents the number of books on the top shelf and $b_{bottom}$ represents the number of books on the bottom shelf, then, for each of the $2^{14}$ ways the books can be distributed amongst the shelves, there are $b_{top}! * b_{bottom}!$ ways the books can be ordered, where $b_{top} + b_{bottom} = 15$.
However, I can't find a way to turn this into a number. This leads me to believe that there is a formula that I should be using that I'm overlooking. What am I missing? Please keep in mind that I'm in the very early stages of this book (page 12, to be precise), so nothing too advanced. 🙂
Best Answer
Breaking it into stages is the right idea, but the stages aren’t the two shelves. The first stage is putting all $15$ books onto the first shelf in some particular order. The second stage is deciding where to ‘cut’ that line of books to transfer the tail end to the second shelf. Can you finish it from there?
Added: There is a way to get the result by thinking first of how to split the books between the shelves, but it’s a bit messier. There are $\binom{15}k$ ways to decide which $d$ books to put on the first shelf. Once we’ve put them there, we can sort them in $k!$ ways, and independently we can sort the $n-k$ books on the second shelf in $(n-k)!$ ways. Since we have to have at least one book on each shelf, $k$ can range from $1$ through $14$, and the desired number is
$$\sum_{k=1}^{14}\binom{15}kk!(n-k)!=\sum_{k=1}^{14}\frac{15!}{k!(n-k)!}k!(n-k)!=\sum_{k=1}^{14} 15!=14\cdot15!\;.$$