Counting squares of NxM lattice

  1. This is not a quiz but I am thinking how to write down a simple math formula to count the total number of squares present in a lattice of NxM points for my 12 year old nephew ? He'll sure be happy if I could turn this into, say, a common sense for pupils like him. :biggrin:

    For example,
    In a 3x4 lattice there are 20 squares.
    I first check 3x3 one (by omitting the last column 3x1) on the right and have
    12+22+32 = 14 squares
    then I check 3x3 one (after omitting the first column) on the right to obtain
    12+22+32 = 14 squares

    So there are 28 squares. But I have 2 columns overlapped between the two squares I have just checked. And I have no clue how to reason to leave out the overlapped part to acquire the correct result.
     
  2. jcsd
  3. Without loss of generality, assume that M >= N.

    Count how many 1x1 squares, how many 2x2 squares and so on up to how many NxN squares. Count those by counting the possible positions for their lower-left corner. For the 3x4 case...

    There are 3x4 = 12 possible positions for the lower left corner of a 1x1 square
    There are 2x3 = 6 possible positions for the lower left corner of a 2x2 square
    There are 1x2 = 2 possible positions for the lower left corner of a 3x3 square.

    ##\sum_{k=0}^{N-1} (N-k)(M-k)##

    But possibly you're way ahead of me and are trying to reduce that to closed form.
     
    1 person likes this.
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook
Similar discussions for: Counting squares of NxM lattice
Loading...