Deriving the Lattice Growth Formula

[musicgold]

Hi,

I am trying to understand how one can derive the lattice growth formula of

L (n) = n^2 ( n + 1)^2 / 4

I looked at 2x2 and 3x3 matrices and could count the squares and rectangles in the figure.
L (2) = 9, L (3) =36 and so on.

However, I am more interested in finding out how the first person who derived this formula would have gone about doing it. Any ideas or pointers are much appreciated.

Thanks,

MG.

 

[Office_Shredder]

What exactly is that supposed to be counting? I tried googling lattice growth formula and your post is the only place it's mentioned on the internet

 

[musicgold]

What exactly is that supposed to be counting?

Sorry about the confusion, maybe I should have been more clear. All the possible squares and rectangles in a 2x2 matrix are represented as L(2) and there are 9 such squares / rectangles. Please see the attached doc. Similarly L(3) represents all possible squares and rectangles in a 3x3 matrix.

 

[Edgardo]

- Take for example the 2x2 square (case n=2). Mark the nodes in the grid such that you
have a total of 9 nodes. We also introduce a cartesian coordinate system such that
we can identify each node via its coordinates (see attachment).



- The question is how do you systematically search for rectangles?
We first notice that a rectangle is completely determined by its bottom-left corner and top-right corner.



- Let's leave the bottom-left corner fixed. How many rectangles are there with
the bottom-left corner fixed at (0,0)?

To answer this question we let the top-right corner move to all allowed positions:

bottom-left corner: (0,0)
=> top-right corner: (1,1), (2,1), (1,2), (2,2)
=> 4 rectangles



- To get all rectangles we also allow the bottom-left corner to move:

bottom-left corner: (1,0)
=> top-right corner: (1,2), (2,2)
=> 2 rectangles

bottom-left corner: (0,1)
=> top-right corner: (1,2), (2,2)
=> 2 rectangles

bottom-left corner: (1,1)
=> top-right corner: (2,2)
=> 1 rectangles

Total number of rectangles: 4+2+2+1 = 9

----

We now have to find a formula for the general case.
Our tactic is to move the bottom-left corner and count the number
of possible positions for the right-top corner.

A pseudo-code for a function that calculates the number
of rectangles is given below:

numberOfRectangles(n):
   counter = 0
   for(j=0...n-1):
      for(i=0...n-1):
         for(y=j+1...n):
	    for(x=i+1...n):
	       counter = counter + 1
   return counter

The first two loops describe the movement of the left-bottom corner
with (i,j) being the position of the left-bottom corner.

The next two loops describe the movment of the right-top corner
with (x,y) being the position of the right-top corner.

You can translate the pseudo-code into mathematics by using the summation symbol:
The inner loop

	    for(x=i+1...n):
	       counter = counter + 1

corresponds to:
\sum_{x=i+1}^n 1 = n-(i+1)+1 = n-1

The next loop

         for(y=j+1...n):
	    for(x=i+1...n):
	       counter = counter + 1

corresponds to:
\sum_{y=j+1}^n \sum_{x=i+1}^n 1 = \sum_{y=j+1}^n (n-i) = (n-i) \sum_{y=j+1}^n 1 = (n-i)(n-j)


The next loop

      for(i=0...n-1):
         for(y=j+1...n):
	    for(x=i+1...n):
	       counter = counter + 1

corresponds to:
\sum_{i=0}^{n-1} \sum_{y=j+1}^n \sum_{x=i+1}^n 1 = \sum_{i=0}^{n-1} (n-i)(n-j)<br /> = ... = (n-j) \cdot \left( n\cdot \frac{(n+1)}{2} \right)


The last loop

   for(j=0...n-1):
      for(i=0...n-1):
         for(y=j+1...n):
	    for(x=i+1...n):
	       counter = counter + 1

corresponds to:
\sum_{j=0}^{n-1} \sum_{i=0}^{n-1} \sum_{y=j+1}^n \sum_{x=i+1}^n 1 = \sum_{j=0}^{n-1} (n-j) \cdot \left( n\cdot \frac{(n+1)}{2} \right)<br /> = ... = \left( n\cdot \frac{(n+1)}{2} \right)^2

I remember having encountered this problem in the excellent book "Thinking mathematically" by John Mason.

 

[musicgold]

Edgardo,

First of all, thanks from the bottom of my heart. That is really helpful.
I understood the most of your solution except two points.

\sum_{x=i+1}^n 1 = n-(i+1)+1 = n-1

I feel that this should be n-i

Also in the following equation,

\sum_{i=0}^{n-1} (n-i)(n-j)= ... = (n-j) \cdot \left( n\cdot \frac{(n+1)}{2} \right)
I am not sure how you got the second part of the answer. I think

\sum_{i=0}^{n-1} 1= (n-i)

 

[Edgardo]

Edgardo,

First of all, thanks from the bottom of my heart. That is really helpful.
I understood the most of your solution except two points.

\sum_{x=i+1}^n 1 = n-(i+1)+1 = n-1

I feel that this should be n-i

Oops, you are right, that's a typo. It should indeed be n-i .

Also in the following equation,

\sum_{i=0}^{n-1} (n-i)(n-j)= ... = (n-j) \cdot \left( n\cdot \frac{(n+1)}{2} \right)
I am not sure how you got the second part of the answer. I think

\sum_{i=0}^{n-1} 1= (n-i)

Let's examine the expression
\sum_{i=0}^{n-1} (n-i)(n-j)

Since we sum over the index i we can pull things that are independent of i
in front of the summation symbol. We see that (n-j) is independent of i:
\sum_{i=0}^{n-1} (n-i)(n-j) = (n-j) \sum_{i=0}^{n-1} (n-i)

Let's concentrate on the sub-expression
\sum_{i=0}^{n-1} (n-i)

The sum is applied to n and to (-i) and we get:
\sum_{i=0}^{n-1} (n-i) = \sum_{i=0}^{n-1} n - \sum_{i=0}^{n-1} i

These sums are evaluated:
\sum_{i=0}^{n-1} n = n \sum_{i=0}^{n-1} 1 = n \cdot n = n^2

\sum_{i=0}^{n-1} i = \frac{(n-1)n}{2}

For the last evaluation I've used http://www.ugrad.math.ubc.ca/coursedoc/math101/notes/integration/sums.html".
We get for the sub-expression:
\sum_{i=0}^{n-1} (n-i) = \sum_{i=0}^{n-1} n - \sum_{i=0}^{n-1} i = n^2 - \frac{(n-1)n}{2} = n^2 - \frac{n^2-n}{2} = \frac{n^2+n}{2}= \left( n\cdot \frac{(n+1)}{2} \right)

Plugging this sub-expression into the expression yields:
\sum_{i=0}^{n-1} (n-i)(n-j) = (n-j) \sum_{i=0}^{n-1} (n-i) = (n-j) \left( n\cdot \frac{(n+1)}{2} \right)

 

[musicgold]

Edgardo,

Now it is clear to me. Thank you very much. Appreciate your efforts.