# Counting squares of NxM lattice

1. Sep 3, 2014

### Medicol

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.

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. Sep 3, 2014

### jbriggs444

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.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted