Counting Ways to Pack Books into Boxes

[throneoo]

Hi. Recently I've been wondering if i could generalize the following problem I randomly had in mind: There are 15 kinds of identical books in a book store . The book store owner packs books into boxes that can contain up to 4 books . Assume that all books are of the same size and those boxes must be completely filled up , how many different ways can the boxes be packed ?

Can anyone give me advice on finding out the relationship between these 2 variables ? Or is there any ?

 

[Robert1986]

Well, you want to know how many ways there are to select 4 books out of 15. Do you see that? There is a well-knows formula for this, but see if you can come up with something on your own. Here is a start:

When packing a box, you can pick from 15 books for the first book. For the second book, you can only pick from 14 books. For the third book, you pick from 13 books, and you pick from 12 books for the 4th book.

 

[who_]

Well, you want to know how many ways there are to select 4 books out of 15. Do you see that? There is a well-knows formula for this, but see if you can come up with something on your own. Here is a start:

When packing a box, you can pick from 15 books for the first book. For the second book, you can only pick from 14 books. For the third book, you pick from 13 books, and you pick from 12 books for the 4th book.

I don't think that works for this case. The books are identical. I think what one should be considering is how many bins have 4 books, how many have 3, etc. In that case, you want to find the number of solutions to 4a+3b+2c+d=15. Unfortunately, I do not believe there is a nice formula for this type of equation in general - however, if the only variable changing is the number of books, then I am sure you could come up with some formula for this scenario.

 

[HallsofIvy]

If the books are identical, the order in the boxes does not matter. If the boxes are identical, the order of the boxes does not matter. Choose 4 books to go into the first box. There are 15(14)(13)(12)= 15!/11!= 15!/(15-4)! ways to do that. You now have 11 books left. Choose 4 books to go in the second box. There are 11(10)(9)(8)= 11!/7! ways to do that. You now have 7 books left. Choose 4 books to go in the third box. There are 7(6)(5)(4)=7!/3! ways to do that. You now have 3 books left to put in the fourth box in any way you wish. There are then (15!/11!)(11!/7!)(7!3!)= 15!/3! ways to do that total.

 

[who_]

If the books are identical, the order in the boxes does not matter. If the boxes are identical, the order of the boxes does not matter. Choose 4 books to go into the first box. There are 15(14)(13)(12)= 15!/11!= 15!/(15-4)! ways to do that. You now have 11 books left. Choose 4 books to go in the second box. There are 11(10)(9)(8)= 11!/7! ways to do that. You now have 7 books left. Choose 4 books to go in the third box. There are 7(6)(5)(4)=7!/3! ways to do that. You now have 3 books left to put in the fourth box in any way you wish. There are then (15!/11!)(11!/7!)(7!3!)= 15!/3! ways to do that total.

That is clearly not right. So if one had 4 books, you are saying that the answer is 4! = 24?

By calculating 15!/11!, you are treating each book differently. Thus, the actual question is how many bins have k books where k is between 1 and 4, inclusive.

 

[throneoo]

here's another example . If each box contains 4 books , 2 different kinds of books produces 5 different ways of packing . At first i thought it was a simple combinatronics problem , but it didn't seem to be when i thought it through .

 

[who_]

here's another example . If each box contains 4 books , 2 different kinds of books produces 5 different ways of packing . At first i thought it was a simple combinatronics problem , but it didn't seem to be when i thought it through .

Could you clarify? Do you have 2 different books? Or 15 books that are of two kinds? If so, how many of each?

 

[uart]

This a standard problem of combination (or permutations) with repeats.

If the order that the books were packed (which is at the bottom of the box etc) was important then it would be a permutation problem. This case is by far the easiest, it is simply 15 ways we can choose the first book, 15 ways to choose the second book and so on. So $15^4$ permutations in this case..

It is unlikely however that we would wish to consider different packing order of the books within the box to correspond to real difference. So treated as a combinations with repeats, we get ${\ }^{18}C_4$ combinations.

To summarize the general case. To choose "r" items from "n" categories with repeats allowed. There are,

$n^r$ permutations.

And

${\ }^{n+r-1}C_r$ combinations.

 

[who_]

In this case however it is unlikely that we would wish to consider different packing order of the books within the box to correspond to real difference. So this would most likely be treated as a combinations with repeats.

This turns out to be ${\ }^{18}C_4$ combinations.

And in general,
$${\ }^{n+r-1}C_r$$

Can you show how you arrive at that answer? I do not get such a large answer (I also assume that the bins are indistinguishable - I don't know if that is a valid assumption or not).

 

[jbriggs444]

As I read the problem, the question is: "In how many distinguishable ways can one box be filled with four books"

(This is the moral equivalent of asking how many distinct four card hands are possible if you ignore suits and add two additional card values, such as "duke" and "earl").

There are five ways that the types can be distributed into the boxes:

1-1-1-1 split
2-1-1 split
2-2 split
3-1 split
4 books of one type

1-1-1-1 split:

There are 15*14*13*12 ways of selecting the book types. Divided by 4 factorial since
order does not matter. 15*14*13*12 / 4! = 1365 possible combinations.

2-1-1 split:

There are 15 ways of selecting the type with 2 books and 14*13 ways of selecting the
remaining two types. Divided by 2 factorial since order of the 1-1 sub-split does not
matter. 15*14*13/2! = 1365 possible combinations

2-2 split:

There are 15 ways of selecting the first pair of types and 14 ways of selecting the second pair. Divided by 2! since the order of the 2-2 split does not matter. 15*14/2! = 105 possible combinations.

3-1 split:

There are 15 ways of selecting the triplet type and 14 ways of selecting the singleton. 15*14 210 possible combinations.

4 of a kind:

There are 15 possibilities.

1365 + 1365 + 105 + 210 + 15 = 3060 distinguishable ways of loading a box.


If the boxes need not be full then we could repeat the above analysis for splits of...

(Three books in the box)
1-1-1 15*14*13/3! = 455
2-1 15*14 = 210
3 15
Subtotal = 680 ways

(Two books in the box)
1-1 15*14/2! = 105
2 15
Subtotal = 120 ways

(One book in the box)
1 15
Subtotal = 15 ways

(No Books in the box)
{} 1
Subtotal = 1 way

Grand total = 3876 ways


Alternately, we could simply redo the analysis but consider "no book" to be a sixteenth type of indistinguishable book. That computation can serve as a sanity check:

1-1-1-1 16*15*14*13 / 4! = 1820
2-1-1 16*15*14/2! = 1680
2-2 16*15/2! = 120
3-1 16*15 = 240
4 16

Total = 3876

*phew*. The answers check.

 

[uart]

Can you show how you arrive at that answer? I do not get such a large answer (I also assume that the bins are indistinguishable - I don't know if that is a valid assumption or not).

One of the best way to prove that is actually to convert the problem to a simple "binary" order form.

It's easiest to explain it by way of example. So say for example you had to get a round of 3 drinks and there were 4 available options of Beer, Coke, Lemonade and Wine (B,C,L,W) on the menu.

Imagine an order-form with three column separators, giving us 4 columns, one for each drink. We could make these 3 column separators by using three binary 1's, and the we could use 0's in each column to specify how many of each drink we required.

So for example, a "code" of 000111 would indicate three beers. A code of 001011 would indicate two beers and one coke. A code of 101010 would indicate one each of coke lemonade and wine, and so on.

So the total number of different combinations is simply the total number of different ways we can position the "r" zeros into the "r+n-1" bit code.

 

[who_]

Ummm, sure - but the original problem states that the books are indistinguishable - so your method doesn't work.

 

[uart]

Grand total = 3876 ways

Hi jbriggs444. The OP specified "Assume that all books are of the same size and those boxes must be completely filled up". So your partial result of 3060 was all that was required.

 

[uart]

Ummm, sure - but the original problem states that the books are indistinguishable - so your method doesn't work.

I think you'll find that he means that all the books of a given kind are indistinguishable, otherwise it doesn't really make much sense.

So 15 kinds of books, let's call them title-1, title-2 ... title-15 for example. All books of type "title-1" are indistinguishable from each other, but are of course distinguishable from title-2 and so on. So its a standard case of combination with repeats.

I really don't understand how you are interpreting this differently. What, there are 15 kinds of books, but they are all identical. That doesn't really make sense!

 

[who_]

Hi all,

Upon rereading the problem, I realized I completely misunderstood the question. Not only did I miss the part that the boxes have to be completely filled up, I also realized that there are 15 kinds of books, not that there are merely 15 identical books. Sorry for the confusion. ><

 

[who_]

Hi all,

Upon rereading the problem, I realized I completely misunderstood the question. Not only did I miss the part that the boxes have to be completely filled up, I also realized that there are 15 kinds of books, not that there are merely 15 identical books. Sorry for the confustion. ><

 

[who_]

Hi all,

Upon rereading the problem, I realized I completely misunderstood the question. Not only did I miss the part that the boxes have to be completely filled up, I also realized that there are 15 kinds of books, not that there are merely 15 identical books. Sorry for the confusion. ><

 

[throneoo]

Could you clarify? Do you have 2 different books? Or 15 books that are of two kinds? If so, how many of each?

I understand the ambiguity here . What I mean in that example is that there are two categories of books , there are infinite books for each category . What matters is the no. of categories of books , but not the quantity for each category. For instance , there are 2 kinds of books : Category A and Category B . Each category of books are enough to fill up infinite boxes . Then there will be 5 different ways to fill up a box that can contain 4 books . Which are :

AAAA
AAAB
AABB
ABBB
BBBB

 

[throneoo]

wow..thanks a lot for providing such satisfying answers

 

[haruspex]

Hi jbriggs444. The OP specified "Assume that all books are of the same size and those boxes must be completely filled up". So your partial result of 3060 was all that was required.

Yes, 3060. But there's a much easier way.
Think of a box as containing four locations for books, and between them, and at the ends of the box, slots for very thin dividers, 5 slots in all. There are 14 dividers to go in each box and any number of them can occupy the same slot. When packing the box, left to right, a divider tells you to switch to the next book type. So the placement of dividers tells you exactly how a box is to be packed, and conversely, for any given choice of books for a box, arranging them in a canonical order determines the appropriate way to place the dividers; so this is a one-to-one mapping.
Now consider the book locations and dividers as just 18 things in a row. Four are book locations, 14 are dividers. Number of possible arrangements is 18 choose 4 = 3060.