Counting squares of NxM lattice

  • Thread starter Medicol
  • Start date
  • #1
223
53

Main Question or Discussion Point

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.
 

Answers and Replies

  • #2
jbriggs444
Science Advisor
Homework Helper
2019 Award
8,932
3,666
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.
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.
 
  • Like
Likes 1 person

Related Threads on Counting squares of NxM lattice

Replies
3
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
7
Views
1K
  • Last Post
2
Replies
29
Views
3K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
1
Views
2K
Top