Counting problem - how many ways....

In summary: ##\binom {15} 2 (1)(14!) = 30!##...3 books...##\binom {15} 3 (1)(14!) = 45!##...4 books...##\binom {15} 4 (1)(14!) = 60!##...5 books...##\binom {15} 5 (1)(14!) = 75!##...6 books...##\binom {15} 6 (1)(14!) = 90!##...7 books...##\binom {15} 7 (1)(14!) = 105!##...8 books...
  • #1
321
20

Homework Statement


Pamela has 15 different books. In how many ways can she place her books on two shelves 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)

Homework Equations

The Attempt at a Solution


apparently the answer is (15!)(14) but I just don't see how.

so this is how I see it..

case 1:

one book on shelf L, 14 books on shelf R

case 2:

two books on shelf L, 13 books on shelf R

case 3:

three books on shelf L, 12 books on shelf R

case 4:

four books on shelf L, 11 books on shelf R

case 5:

five books on shelf L, 10 books on shelf R

case 6:

six books on shelf L, 9 books on shelf R

case 7:

seven books on shelf L, 8 books on shelf R

case 8:

eight books on shelf L, 7 books on shelf R

case 9:

nine books on shelf L, 6 books on shelf R

case 10:

ten books on shelf L, 5 books on shelf R

case 11:

eleven books on shelf L, 4 books on shelf R

case 12:

twelve books on shelf L, 3 books on shelf R

case 13:

thirteen books on shelf L, 2 books on shelf R

case 14:

fourteen books on shelf L, 1 book on shelf RI'll just go backwards I guess

for case 14, if you choose 1 of the 15 books and put it on shelf R, shelf L can have 14! combinations of the remaining books. Now if you put that book that was on shelf R and exchange it with a different book on shelf L, shelf L can have 14! new combinations of books because we switched the two books out.

You can do this for all 15 books

so just for case 14 you get a combination of: (15)(14!)

then for case 13, you have 2 books on shelf R, 13 on shelf L. shelf L can be arranged 13! ways while shelf R can be arranged 2! ways. so (13!)(2!). If we only switch out one book, and keep another, it will be (13!)(2!)(14) because there are 14 possible books that we can switch out while keeping one of the books.

Then there are (13!)(2!)(14)(15) combinations because there are 15 books total that you're going to useI'm just going to stop here. My answer leads me to adding all the the combinations in all of my cases, and just adding case 14 and 13 is already an extreme overestimate of the answer that the book has given me.

I just don't understand where my logic is failing though. Can anyone let me know?
 
Physics news on Phys.org
  • #2
The trick here is in finding the simplest way to think about the problem. Try this - how may arrangements are there of 15 books? Once you have an arrangement, how many ways are there to put a space between two of the books? (You can then put the two batches formed this way on separate shelves.)
 
  • #3
tnich said:
The trick here is in finding the simplest way to think about the problem. Try this - how may arrangements are there of 15 books? Once you have an arrangement, how many ways are there to put a space between two of the books? (You can then put the two batches formed this way on separate shelves.)
So there are 15! arrangements. Then there are 14 cases like I listed.

That's 15!*14 its starting to make sense now.. but I just don't see why my logic is faulty in the OP.

for example 1 book on shelf L, 14 on shelf R. You have 15 books that can be on shelf L, 14! combinations on shelf R = (15)(14!) + for the other cases

so add that to

2 books on shelf L, 2! possibilities, you can choose 15 books so (2!)(15), on shelf R you have (13!) so (2!)(15)(13!)

and so on
 
  • #4
Rijad Hadzic said:
So there are 15! arrangements. Then there are 14 cases like I listed.

That's 15!*14 its starting to make sense now.. but I just don't see why my logic is faulty in the OP.

for example 1 book on shelf L, 14 on shelf R. You have 15 books that can be on shelf L, 14! combinations on shelf R = (15)(14!) + for the other cases

so add that to

2 books on shelf L, 2! possibilities, you can choose 15 books so (2!)(15), on shelf R you have (13!) so (2!)(15)(13!)

and so on
For 1 book on the first shelf, there are ##\binom {15} 1## ways to choose which books are in each group. For the first group there is 1 way to arrange the group, for the second group there are 14! ways. So the number of arrangements for one book on the first shelf is
##\binom {15} 1 (1)(14!) = 15!##

Similarly, for 2 books on the first shelf, there are
##\binom {15} 2 (2!)(13!) = 15!## arrangements

and for k books on the first shelf, there are
##\binom {15} k (k!)(15-k)! = 15!## arrangements

How many possible values of k are there?
 
  • #5
tnich said:
For 1 book on the first shelf, there are ##\binom {15} 1## ways to choose which books are in each group. For the first group there is 1 way to arrange the group, for the second group there are 14! ways. So the number of arrangements for one book on the first shelf is
##\binom {15} 1 (1)(14!) = 15!##

Similarly, for 2 books on the first shelf, there are
##\binom {15} 2 (2!)(13!) = 15!## arrangements

and for k books on the first shelf, there are
##\binom {15} k (k!)(15-k)! = 15!## arrangements

How many possible values of k are there?
Thank you! I think I'm starting to understand now! There are k= 14 books.

Truly I thank you for the reply and I don't understand why I couldn't see this problem this way the first time... IDK what I was thinking in the OP
 
  • Like
Likes tnich

1. How do you approach counting problems?

When facing a counting problem, the first step is to determine if it is a permutation or combination problem. Permutation problems involve arranging items in a specific order, while combination problems involve selecting items without regard to order. Once this is determined, the appropriate formula can be applied.

2. What is the difference between permutations and combinations?

Permutations involve arranging items in a specific order, while combinations involve selecting items without regard to order. For example, if there are 3 items (A, B, and C), the possible permutations are ABC, ACB, BAC, BCA, CAB, and CBA. The possible combinations are ABC, ACB, and BAC.

3. How do you calculate the number of ways to choose r items from a set of n items?

The formula for combinations is nCr = n! / (r!(n-r)!), where n is the total number of items and r is the number of items being chosen. For permutations, the formula is nPr = n! / (n-r)!.

4. Can the counting principle be applied to all counting problems?

Yes, the counting principle can be applied to all counting problems. The counting principle states that if there are m ways to do one thing and n ways to do another, then there are m x n ways to do both. This principle can be extended to more than two options as well.

5. How do you account for repetitions in a counting problem?

If repetitions are allowed in a counting problem, the formula for combinations and permutations must be adjusted. For combinations, the formula becomes nHr = (n+r-1)! / (r!(n-1)!). For permutations, the formula becomes nPr / p1!p2!...pk!, where p1, p2, etc. represent the number of repetitions for each item.

Suggested for: Counting problem - how many ways....

Replies
17
Views
1K
Replies
18
Views
1K
Replies
4
Views
965
Replies
4
Views
2K
Replies
3
Views
1K
Replies
1
Views
2K
Replies
2
Views
689
Replies
9
Views
743
Back
Top