Say I have a long rectangular hole of size n and then a bunch of smaller rectangles of different lengths a, b, c, etc such that the sum of their lengths is <=n.

I am trying to figure out the number of distinct permutations. For instance, if I had a hole of length 4 and two rectangles of length 2, there's only one way to arrange that. But if I had one of length 3 and one of length 1, that's two ways to arrange it.

If I had a hole of length 4 and a sub-rectangle of length 2, there are 3 ways, and so on.

Edit for clarification: The lengths are integers only, and they can only be "snapped" in at integer intervals (so you can't place a rectangle at, say, 1.233249 and then claim there are infinitely many ways to insert a rectangle). Area also doesn't matter... the height of the rectangles are all the same. It's only the lengths that differ.

Is there a simple mathematical combinatoric that can be applied here?

  • $\begingroup$ For clarity: so $n$ is a length, not the area of the rectangle and you want a solution to the discrete problem (ie everything has integer length and can only be placed at integer positions not at 2.54234...)? $\endgroup$ – example Apr 3 '12 at 13:54
  • $\begingroup$ Yes, exactly right. Edited the original post for clarity. $\endgroup$ – WhatsInAName Apr 3 '12 at 13:57
  • $\begingroup$ What do you mean by a hole of length 4 and sub- rectangle of length 2, there are 3 ways? $\endgroup$ – Hugo Apr 3 '12 at 14:08
  • $\begingroup$ Say the hole looks like this: oooo. The rectangle of length 2 looks like this: RR. There are three ways to arrange: RRoo, oRRo, ooRR $\endgroup$ – WhatsInAName Apr 3 '12 at 14:09

You are asking about partitions if the order doesn't matter, and compositions if it does. It sounds like 13 is different from 31, so compositions are what you are after.

| cite | improve this answer | |
  • $\begingroup$ This is very informative, and even has combinatoric info listed. I'll count this as an answer. Thank you! $\endgroup$ – WhatsInAName Apr 3 '12 at 14:38

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.