Number of rectangles in MxN matrix.

Problems

1. Count number of squares in chessboard?
2. Count number of rectangles in MXN rectangle
3. Squares in rectangle

Lets answer them 1 by 1.

Solution

Number of squares in chessboard having 8X8 grid.
There are four 7x7 squares, one aligned with each corner.   There are nine 6x6 squares, etc.  So the sum of the first 8 squares 1+4+9+16+25+36+47+64=204 is the answer.  In general, the sum of the first n squares is given by the formula

(2n³+3n²+n)/6

Now lets move to next.
Number of rectangles in MXN rectangle
The answer to this question is the same as the answer to another question:

How many ways can I draw two horizontal lines and two vertical lines through an array of (m+1) by (n+1) dots?
(Think of the dots formed at the corners of the little squares within the rectangle)

The two horizontal lines can be drawn C(m+1,2) ways, and the two vertical lines can be drawn C(n+1,2) ways, so the total number of rectangles within an m x n rectangle is

C(m+1,2) C(n+1,2)

Squares within rectangle
How many squares can be found within an m x n rectangle?  (m > n)
To answer this question, start with an n x n square, and then you know the number of squares in this portion of it from the first section:

(2n³+3n²+n)/6

Now, consider adding one row of squares at the bottom, making it an n+1 by n rectangle.  Think of the dots formed at the corners of the little squares you added to make the bottom row.   Now, for every pair of newly-added dots, you can find one new square.  So the number of new squares you can find in the now larger rectangle is the number of pairs of n+1 dots, which is C(n+1,2).  If you need convincing, there's another way to think of it.  By adding a new row of n little squares, you can now find within the large rectangle one new n x n square, two new n-1 x n-1 squares, three new n-2 x n-2 squares, etc.  So the number of new squares added this way is the sum of the first n counting numbers, which is C(n+1,2).

Now, add another row of squares at the bottom, making it an n+2 by n rectangle.  This adds the same number of new squares, C(n+1,2).

Now I'm sure you see the picture.  The number of squares that can be found within an m x n rectangle (m > n) is given by this formula:

(2n³+3n²+n)/6 + (m-n) C(n+1,2)

 References
http://2000clicks.com/mathhelp/CountingRectangles.aspx