## A problem concerning counting

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 ?
 PhysOrg.com mathematics news on PhysOrg.com >> Pendulum swings back on 350-year-old mathematical mystery>> Bayesian statistics theorem holds its own - but use with caution>> Math technique de-clutters cancer-cell data, revealing tumor evolution, treatment leads
 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.

 Quote by 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.
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.

Recognitions:
Gold Member
Staff Emeritus

## A problem concerning counting

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.

 Quote by 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.
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.
 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 .

 Quote by 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 .
Could you clarify? Do you have 2 different books? Or 15 books that are of two kinds? If so, how many of each?
 Recognitions: Science Advisor 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.

 Quote by uart 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).
 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.

Recognitions:
 Quote by 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).
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.
 Ummm, sure - but the original problem states that the books are indistinguishable - so your method doesn't work.

Recognitions:
 Quote by jbriggs444 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.

Recognitions: