A problem concerning counting

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_

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_

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_

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 [itex]15^4[/itex] 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 [itex]{\ }^{18}C_4[/itex] combinations.

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

[itex] n^r [/itex] permutations.

And

[itex]{\ }^{n+r-1}C_r[/itex] combinations.

who_

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

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

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

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, lets 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. ><