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. :)