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. jbriggs444

    jbriggs444 1,937
    Science Advisor

    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 this thead via email, Google+, Twitter, or Facebook

Have something to add?

0
Draft saved Draft deleted
Similar discussions for: Counting squares of NxM lattice
Loading...