How many subrectangle exists on a m x n grid

Question

Given a m x n grid, how many unique sub-rectangles exist on such a grid?

For example,

1 x 1 grid has 1 sub-rectangle.

1 x 2 grid has 3 sub-rectangles.

I am looking for a general formula that can be used to directly compute the number existing sub-rectangle.

Answer 1

An alternate solution,

In a m*n grid, we have m+1 lines and n+1 lines intersecting.

We use the fact, a rectangle can be formed by choosing a intersection point between these lines and another point which is not in either the horizontal or vertical line.

So, number of ways to choose a intersection point is (m+1)(n+1), and subsequently the number of ways to choose the second point is [which is number of ways to choose a intersection point excluding the points in the same horizontal and vertical line] is ((m+1)(n+1)-n-m-1) (minus 1 to avoid the already chosen intersection point)

Now consider a 1x1 grid , we use the fact this grid can be counted 4 times each uniquely by the 4 points.

Therefore the total number of rectangles which can formed is [(m+1)(n+1)((m+1)(n+1)-n-m-1)]/4

which can be simplified further to [(m+1)(n+1)(m)(n)]/4

Answer 2

There are ((m+1)mn*(n+1))/4 rectangles including squares [subset of rectangles]

Answer 3

The correct answer should be (m(m+1)n(n+1))/4 minus the number of squares in the rectangular grid.

Answer 4

I found a nice solution,
Lets look at the table borders of the grid.
And to create a rectangle we need four points on the borders.
2 points horizontal and 2 vertical

for example (n = 4, , m = 5)
Note that the choice is for N + 1 and M + 1 Because we look at the borders and not the rectangles themselves

Here is an example of one choose:

We can calculate all the possible choices to chose 2 horizontal point and 2 vertical point using the binomial formula:

Answer 5

Same answer as @Thomash provided, but with a bit more explanation, posting for posterity:

If you can figure this out in one dimension, it's easy to move it into two dimensions.

Let's look at a 1x5:

 5 1x1 squares
+4 1x2 squares
+3 1x3 squares
+2 1x4 squares
+1 1x5 squares = 15 squares.

The formula for this is simple: sum = n(1 + n)/ 2. In the case of 5, you want 5(1+5)/2 = 15.

So, to get your answer, just do this for n and m, and multiply them:

sumN = n(1+n)/2
sumM = m(1+m)/2
totalRectangles = nm(1+n)(1+m)/4

Answer 6

For this lets assume you've m columns and n rows:

. . . .
. . . .
. . . .

In above grid, m is 4 and n is 3. Let say you need to know how many rectangle you can form if you select top-left point. If you select top left-corner i.e.

* . . .
. . . .
. . . .

You have have 3 point to choose in right and 2 points to choose at bottom, therefore total combinations are: 3*2 = 6.

Therefore total number rectangle you can form will correspond to total number of rectangles at each point starting from (0, 0) (top left assume to be 0, 0) till (m-1, n-1).

If you try to find summation of this:

[(m-1)*(n-1) + (m-2)*(n-1) + (m-3)*(n-1) ... + (n-1)] + 
[(m-1)*(n-2) + (m-2)*(n-2) ... + 1*(n-2)] +
[(m-1)*(n-3) + (m-2)*(n-3) ... + 1*(n-3)] +
... 

Which is equal to

(n-1)*(1 + 2 + .. + m-1)
+
(n-2)*(1 + 2 + .. + m-1)
+
.
.
+
1*(1 + 2 + ... + m-1)

So you get

(1 + 2 + ... + n-1) * ( 1 + 2 + 3 ... + m-1)
= mn(n-1)(m-1)/4

Since m and n is your case are not number of point but number of line segments formed. Above formula can be transformed:

m = m + 1
&
n = n + 1

And it becomes

(n+1)(m+1)mn / 4

Answer 7

The answer is m(m+1)n(n+1)/4.

a rectangle is defined by its two projections on the x-axis and on the y-axis.

projection on x-axis : number of pairs (a,b) such that 1 <= a <= b <= m = m(m+1)/2

idem for y-axis