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

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.

---

Answer 3

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.