I have a number of books (n). They all have different a different thickness and mass.

I know that there are (2^n)-1 combinations to place the books. The order of the books does not matter.

However I want to understand what happens when I introduce a constraint into these problem. Such as the fact that a maximum of 6 books are able to be placed next to each other, because 6 x the 6 thinnest books still fits but 7 x the 7 thinnest books does not.

How many possible combinations are there then?

For example if N = 4 (a,b,c,d) we can receive the following options:

a b c d ab ac ad bc bd cd abc abd acd bcd abcd

which equals to 15 = (2^n)-1 combinations. Now if my maximum constraint is 2, the results would be:

a b c d ab ac ad bc bd cd

Which is equal to 10 combinations. How do I calculate this?

What I am ultimately trying to get to is the most efficient way of placing these books on shelves. but the number of books can go into the hundreds.


There are $2^n-1$ non-empty subsets of the set of books. This doesn't say anything about the order.

To choose $r$ items out of $n$, again without respect to order, you want ${n\choose r}=\frac {n!}{r!(n-r)!}$

You could see here to start.

  • $\begingroup$ so if my r = 2 in my example. The result would have to be (4 2) + (4 1) = 6 + 4 = 10 which is correct. But my question is the sumation. Is there a general equation for this? or is it just a SUM? $\endgroup$ Oct 1 '13 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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