Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm having a discussion with a co-worker over the number of permutations in a bin packing problems as follows.

There are two bins each of which can hold 6 cu ft. A package can be from 1 - 6 cu feet, there can be from 1 - 12 packages. How many permutations are possible?

It's been a great many years since either of us have done any formal math but it seems to me the problem space isn't all that large due to the constraints, though the problem is NP complete. We found a few web pages talking about different approaches to bin packing but nothing really on how to determine number of possible permutations.

share|improve this question
    
This is a basic clarification. When you ask for permutations, are you implying that ordering matters across bins? i.e., if I have a 6 cu.ft. package in the first and two 3 cu. ft. packages in the second, is it counted as different from an arrangement where there are two 3 cu. ft. packages in the first and 6 in the second? If a bin has (1,2,3) is it different from (2,3,1)? –  svenkatr Mar 23 '11 at 21:44
    
If none of the orderings matter, you should be asking for the number of combinations. –  svenkatr Mar 23 '11 at 21:45
    
Sorry, it's been too long since my formal education as I implied, yes I mean number of combinations not permutations. (1, 2, 3) is the same as (3, 2, 1) as long as they are both in the first bin. –  Doug-W Mar 24 '11 at 1:14
add comment

1 Answer

In your problem, each bin is filled independently of the other. Therefore, you need to find out the number of ways you can fill up one bin and square that number.

If $n$ is the capacity of one bin, the number of distinct ways of filling it with packages is given by the partition number $p(n)$. Check out these articles for more details on partition functions

http://en.wikipedia.org/wiki/Partition_%28number_theory%29

http://mathworld.wolfram.com/Partition.html

For your question $n = 6$. Therefore, the number of possible arrangements is $p(n)^2 = 11^2 = 121$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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