4
$\begingroup$

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

3 Answers 3

2

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!\;.$$

  • 0
    Let me think about it for a few minutes and I'll get back to you. Thanks!2012-06-14
  • 0
    If the first stage is putting all 15 books onto the first shelf in some particular order, then the number of possible outcomes for the first stage is $15!$. If the second stage is then deciding where to 'cut' that line of books to transfer the tail end to the second shelf, then the number of outcomes for the second stage is 15. Then, by the rule of product, there are $15! * 15$ ways to carry out this operation. Correct? Then, how do I account for the rule that says I have to have at least one book on each shelf? Does this make any difference?2012-06-14
  • 0
    @BrewerHimself: Yes, it does, in the second stage. There are actually $15+1=16$ potential cut points, including before the first and after the last book, but you can’t use the two on the ends: you have to use one of the $14$ cut points that actually have a book on both sides of them. Thus, you get a total of $14\cdot15!$.2012-06-14
  • 0
    Thanks! In my original post, I commented on there being 2^14 ways to sort the 15 books across the 2 shelves. Was I correct? Is this relevant to my final answer? Unfortunately, I didn't have the money to get the solutions manual when I bought the book, so I can't really check my answer.2012-06-14
  • 0
    @BrewerHimself: Not quite right: there are $2^{15}$ ways to decide for each book on which shelf it goes, but $2$ of those ways put all $15$ books on one shelf, so there are $2^{15}-2=2\left(2^{14}-1\right)$ ways to split the books between the shelves if order doesn’t matter and you must have at least one book on each shelf. The problem with approaching it this way is that you’re left (as you discovered!) without any general way to count the arrangements on each shelf, because you don’t have a handle on the number of books on each shelf.2012-06-14
  • 0
    Then we can agree that the answer is $15! * 14 = 18,307,441,152,000$ distinct ways to align the books? That's a lot. My mind is blown.2012-06-14
  • 0
    @BrewerHimself: Looks good to me! (By the way, you might want to check out the addition that I made to my answer: in combinatorics there’s often more than one way to do something, and you’ll find that the more ways you know, the easier it gets.)2012-06-14
  • 0
    Thanks for your help! As a last request, if you could tell me what the notation $\binom{a}{b}$ is called, that would be great. I'm not familiar with it and I'd like to know what it means. **EDIT** According to Wikipedia, this is a Binomial coefficient.2012-06-14
  • 0
    @BrewerHimself: That’s a [binomial coefficient](http://en.wikipedia.org/wiki/Binomial_coefficient); it turns out to be the number of $b$-element subsets of a set of $a$ things. You’ll be seeing a *lot* of binomial coefficients. I think that you’re using Grimaldi; in the 4th ed., at least, they appear in the very next section, 1.3.2012-06-14
-1

Begin by starting with the number of permutations there are for 15 books, assuming they're all on one shelf, which is $15!$. With two shelves, there are $16$ ways, or "cut points" as Brian M. Scott aptly phrased, to arrange the $15!$ arrangement of books. $14$ of these cut points are in-between each book, and two of them are on each end of the shelf of $15$ books.

Since we need at least one book per shelf, we do not want to use either cut point at the ends of the $15$ books, leaving us with $14$ different arrangements of $15!$.

So, $15! \cdot 14$ is indeed the correct answer. The most simple way to break it down is to imagine $2$ shelves with $2$ books. If you can have $2$ books on a shelf, and $0$ on the other, there are $6$ ways to arrange the books. This is because the $2$ books have $3$ cut points, and $2!$ ways to arrange them. $2! \cdot 3 = 6$. If you need at least one book per shelf, then there is only one cut point, right between the $2$ books, thus making $2$, $(2! \cdot 1)$, ways to arrange the books.