This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.
How many (possibly overlapping) squares are in an mxn grid? Assume that all
the squares have their edges parallel to the edges of the grid.
combinatorics/grid.dissection.s
Given an n*m grid with n > m.
Orient the grid so n is its width. Divide the grid into two portions,
an m*m square on the left and an (n-m)*m rectangle on the right.
Count the squares that have their upper right-hand corners in the
m*m square. There are m^2 of size 1*1, (m-1)^2 of size 2*2, ...
up to 1^2 of size m*m. Now look at the n-m columns of lattice points
in the rectangle on the right, in which we find upper right-hand
corners of squares not yet counted. For each column we count m new
1*1 squares, m-1 new 2*2 squares, ... up to 1 new m*m square.
Combining all these counts in summations:
m m total = sum i^2 + (n - m) sum i i=1 i=1 (2m + 1)(m + 1)m (n - m)(m + 1)m = ---------------- + --------------- 6 2 = (3n - m + 1)(m + 1)m/6
 
Continue to: