How many different rectangles (in terms of area) can fit in a 20-unit-wide square?

Question

How many different rectangles (in terms of area) can fit in a 20-unit-wide square? The rectangles can be squares, and their dimensions are integers.

Answer 1

If you're looking for the number of different areas realizable by fitting rectangles in a 20x20 square with (integer-length) edges parallel to the coordinate axes, the answer is the number of elements in {$ \{ x \times y | x,y \in \{ 1..20 \} \} $}. In Haskell, length . List.nub . sort $ [x*y| x<-[1..20] , y<-[1..20]] evaluates to 152.

Answer 2

The answer is 27. The 28th triangular number is 406, so 28 is out, but you can fit rectangles in the square so that 1+...+21+24+25+27+28+30+35=400. 1-20 are 1xn rectangles, and you can arrange them so that you get a 10x19 rectangle left over. Cut off a stripe with 3x9 and 3x10, so you have 7x19 left. Chop off the other direction with 3x7 and 4x7. The remaining 7x12 rectangle is partitioned into 2x12, 5x5, and 5x7.

Answer 3

If the unclear question means "how many ways can you partition the 20x20 unit region into multiple subregions each of which is a rectangle integer unit dimensions, with widths and lengths greater than zero?" then you've got a different answer.

There is $1$ way to partition it into $400$ different 1x1 squares.

There is $1$ way to partition in into $1$ large 20x20 square.

There are $0$ ways to partition it using $399$ {1x1} squares, because using $399$ {1x1} squares leaves a {1x1} area to be filled, which can only be filled by a {1x1} square yielding $400$ {1x1} squares, which is already counted above.

Using $398$ {1x1} squares, there are $20\times 19 \times 2 = 760$ ways to partition it: with $398$ 1x1 squares and $1$ 2x1 rectangle. The 2x1 rectangle can be posed vertically at $20$ different $x$-positions by $19$ different $y$ positions, or it can be posed horizontally at $19$ different $x$-positions by $20$ different $y$ positions, yielding $20 \cdot 19 \cdot 2$.

You can do similar combinatorics for using $397$ unit squares = $397$ {1x1} + $1$ {3x1}. Placing the long rectangle vertically yields $20 \ times 18$ ways, horizontally also yields $18 \times 20$ ways, totalling $720$ ways.

It gets more fun at $396$ unit squares, because the four squares you've removed from the first part of the solution above can be drawn as just $1$ {2x2} square, or as $2$ {1x2} squares (both of which can take on vertical or horizontal orientations), or as $1$ {4x1} square drawn either vertically or horizontally. The total number of these combinations can be calculated in a similar manner.

And keep going on up to using $0$ (zero) {1x1} squares: the single $1$ {20x20} square fitting in the area.

---

If you mean how many differently dimensioned rectangles could be drawn, one at a time, into a region of 20x20, then let

the x-dimension can vary from 1 to 20

the y-dimension can vary from 1 to 20

yielding $20\times 20=400$ different size rectangles if orientation matters. Orientation matters if a vertical {1x20}-sized rectangle is considered as being different from the horizontal {20x1}-sized rectangle.

If orientation does not matter, then in this manner of counting each rectangle is counted twice as an $m \times n$ rectangle and as an $n \times m$ rectangle, so divide that in half resulting in $200$ different dimensioned rectangles could be drawn, one at a time, into a region of 20x20, if orientation does not matter.

There is also Scott Carnahan's approach in this question, which yields the answer $27$ using triangle numbers.

If that is the correct answer, my answer above should match it, however, my answer is in the form of a heuristic rather than in closed form.

3rd way Here is an example that divides 20x20 into 29 rectangles: The first column is the running count of rectangles so far, the second column is the y-position of the rectangles, the third column tells how to subdivide the length of that rectangle into two parts.

(count) y-pos   xwidth of rects
 2       1      19 + 1
 4       2      18 + 2
 6       3      17 + 3
       ...
18       9      11 + 9


19    10+11    19x2 + 1x2*
21    12+13    18x2 + 2x2
23    13+14    17x2 + 3x2
25    15+16    16x2 + 4x2
27    17+18    15x2 + 5x2
29    19+20    14x2 + 6x2

Notice that the {1x2} rectangle is duplicated vertically in the first line and horizontally in the 10th and 11th lines (marked with an asterisk). This yields $29$ different rectangles, with only one duplication, whereas Scott Carnahan's approach has much more than one duplication of the {1x1} square}

So of course, the answer depends exactly on what you mean specifically by the question.

---