How many subrectangle exists on a m x n grid
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
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