Date: Sep 8, 2006 9:56 PM
Author: Oliver  Stemforn
Subject: How many rectangles are in an n by n square array of dots?

Let the n by n dots be in one plane, and let n be equal to or greater than 2.  Rectangles here are understood to be squares or non-square rectangles.  A rectangle counts only when each of its four vertices coincides with one of the dots of the array.*** 

Can you come up with a polynomial in terms of n for the total number of rectangles for a general n by n array?

*** For instance, if the dots were
(0,0),(0,1),(1,0), and (1,1), (meaning n = 2) then there would be a total of one rectangle for this array.
(In this case it would be described more specifically as a square if connected.)