Register to reply

Counting squares of NxM lattice

by Medicol
Tags: counting, lattice, squares
Share this thread:
Medicol
#1
Sep3-14, 02:50 PM
P: 54
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.
Phys.Org News Partner Mathematics news on Phys.org
Researcher figures out how sharks manage to act like math geniuses
Math journal puts Rauzy fractcal image on the cover
Heat distributions help researchers to understand curved space
jbriggs444
#2
Sep3-14, 04:08 PM
P: 999
Quote Quote by Medicol View Post
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.


Register to reply

Related Discussions
Not Linear counting, 3D counting billions of billionths General Math 3
Counting multiplicities of a particle lattice Advanced Physics Homework 2
Primitive lattice vectors, reciprocal lattice, wigner seitz cell Atomic, Solid State, Comp. Physics 1
One-dimensional monatomic chain; square lattice; hcp close packed 2D lattice Advanced Physics Homework 0
Does any lattice or lattice shape has a periodic boundary condition? Classical Physics 4