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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Let me think about it for a few minutes and I'll get back to you. Thanks! $\endgroup$ – BrewerHimself Jun 14 '12 at 6:19
  • $\begingroup$ 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? $\endgroup$ – BrewerHimself Jun 14 '12 at 6:25
  • $\begingroup$ @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!$. $\endgroup$ – Brian M. Scott Jun 14 '12 at 6:27
  • $\begingroup$ 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. $\endgroup$ – BrewerHimself Jun 14 '12 at 6:30
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Jun 14 '12 at 6:34
0
$\begingroup$

okay bro, first things first.there are a total of 2^15-2 ways of distributing those books on two shelves not 2^14.There are two ways in which you can count the distributions(combinatons not arrangements).

1:you have 15 books say book1,book2,...book15. Now book1 has 2 choices (to be placed on shelf 1 or shelf 2),now for every choice of book1,book2 also has 2 choices(i.e. if book1 is on shelf 1 book 2 can be on shelf1 or shelf2 or if book1 is on 2nd shelf then book2 can be on shelf1 or shelf2) similarly book3 has 2 choices for every choice of book1 and book2 continuing in this way the total number of distrbutions of the books is 2^15(Think on why we multiplied the choices of the books to get the answer).Now we have counted two cases that are not possible i:all fifteen books on shelf1 , ii:all fifteen books on 2nd shelf. So we remove those counts and get 2^15-2..

2.another way of counting the distributions is that we look at only one shelf say shelf1. now we have a total of fifteen books so if shelf1 has 1 book on it,it can be any one of the fifteen books(the reason we are considering only one shelf is that we assume that the rest of the books will be on the other shelf,i.e. if shelf1 has 1 book on it then the rest 14 are on shelf2) so,we can select 1 book from total of 15 books in C(15,1) ways and place it on shelf1(the rest 14 will be on shelf2,so C(15,1) is actually number 1,14 combination),similarly shelf1 can have any two books on it out of 15,number of ways of selecting 2 books from 15 is C(15,2) continuing this way shelf1 can have 14 books on it but they can be any 14 out of 15 so we select 14 books out of 15 in C(15,14) ways and place it on shelf1. Finally total number of combinations is C(15,1)+C(15,2)+C(15,3)+..C(15,14),now you cant add these terms yet because there is a formula (binomial theorem) C(n,0)+C(n,1)+...C(n,n)=2^n you can see the sum that we get does not have the terms C(15,0) and C(15,15) so we add it and subtract it from the sum. So, total combinations = C(15,0)+C(15,1)+C(15,2)+...C(15,15)-C(15,0)-C(15,1)=2^15-2. Okay now you have to understand the difference between combinations and arrangements to solve this question.

NOW..

COMBINATIONS:

when we count the ways in which we can split the books on the two shelves without caring what their position is on their respective shelves then we are counting only the distributions(combinations) not the arrangements.So now lets see the ways in which we can split these books between the shelves. You can keep 1 book on shlef1 and rest 14 on shelf2(1,14 combination),then you can keep two books on shelf1 and rest 13 on shelf2(2,13 combination) continuing this way you get the 14,1 combination(14 books on shelf1,1 book on shelf2).We can only see 14 ways of splitting these books((1,14),(2,13)...(14,1)),but we know total ways in which we can split the books is 2^15-2,HOW??. Actually there are 14 unique ways of splitting these books and each way in itself is of different types.If you keep book1 on shelf1 and rest on shelf2 this is one type of 1,14 combination,if you keep book2 on shelf1 and rest 14 on shelf2 this is another type of 1,14 combination so adding all the types of unique combinations we get the total number of combinations.

ARRANGEMENTS:

Now, imagine any combination of the books lets say 2 books on shelf1(say book1 and book2) and the rest 13 on shelf2, now if i keep the two books on shelf1 as book1,book2 and rearrange the books on shelf2 i get different arrangements and if i keep the two books on shelf1 as book2,book1 and rearrange the books on shelf2 i get different arrangements,So imagine it this way you keep shelf1 books as it is and rearrange the books on shelf2 then rearrange the books on shelf1 once and rearrange the books on shelf2 in all possible ways you can, you will get differnet arrangements.In simple words for every arrangement of books on shelf1 you can arrange the books on shelf2 in all the way you can and you will get different arrangements. NOW lets count.. so. if i keep 4 books on shelf1 and 11 on shelf2 i can arrange books on shelf1 in 4! ways and for every arrangement of the books on shlef1 you can arrange the books on shelf2 in 11! ways so total arrangements is 4!.11! but the combination 4,11 is of C(15,4) or C(15,11) types so total arrangements is = 4!.11!.C(15,11).In general if there are r books on shelf1 and 15-r books on shelf2 for every arrangement of the books on shelf1 books on shelf2 can be arranged in (15-r)! ways and the combination r,(15-r) is of C(15,r) or C(15,15-r) ways so total arrangements = sum(r!.(15-r)!.C(15,r)).....where r varies from 1 to 14.Now you know C(15,r)=15!/(15-r)!.r! hence every term in the sum becomes 15! and we have 14 terms, so answer=14.15!.

ADDITIONAL:

First of all why are you doing 15-1 to get 14.You mean to say "total no.of books - least no.of books that will be on any shelf",this does not mean anything.First decide what do you want to count is it the combination or the arrangement,Then if you want to count combinations start by knowing what combination means then come up with a systematic way to do that, do the same for arrangements.

1.Rule of sum or product? or is it C(n,r) or P(n,r)??(we always add):

First,i suggest you to find the meaning of every formula and rule,like P(n,r) means "adding all the arrangements of r objects selected from n distinct objects".So understand the result of each and every formula and rule.

Now if you are confused when to use rule of sum or rule of product or when to use C(n,r) and when do i use P(n,r), then know that actually we only add,we use these rules to fasten our calculations (same is for all the formulas i.e sum(C(n,r)) r varies from 0 to n = 2^n,i.e don't directly jump onto the formulas use them to fasten your calculations).Now its all about that case..Now, if you have 10 books and you are asked if you can select one book out of it ,in how many ways can you do that.The answer is 10,because case 1 you pick book1,case 2 you pick book2 so if you add up all the cases you get the answer.Now imagine if you are asked to count the total fingers you have,you can count your fingers one by one OR you say i have same fingers on both hands so i count the fingers on one hand and multiply it by 2(The rule of product was used to fasten our calculation.Also whenever you see multiplication always see it as "a certain number of things for every thing").Now consider this question,the first case is that you split the books in 1,14 combination but this case itself is of 15 types,now to count case 1: first we have to count the arrangements,how do we do that ?, we come up with a way of imagining those arrangements(i.e keeping books on shelf1 as it is then arranging the books on shelf2 in every way we can,then arrange the books on shelf1 once and arrange the books on shelf2 in every way we can.),so when we imagine all the arrangements we realize that we need product rule and the P(n,r) to fasten our calculations,then every type of 1,14 combination has the same no.of arrangements so instead of adding we will just use rule of product,Similarly we count all the different cases and add them up.

2. Whenever you approach a counting problem,divide it into cases count each case in a systematic way by imagining what it will look like,then add up all the cases.Remember to always add and use the formulas to only fasten your calculations,don't directly jump on them.

3. Finally there may be times when you come up with a wrong way of counting,then don't simply discard that method rather justify yourself why it is wrong.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.