[drunner2007]

Suppose that you have a rectangular x grid of points. How many squares can be formed with vertices as grid points? There are no orientation restrictions on the squares.


I came up with a moderately ugly double summation that appears to work in the general case, but I need confirmation and I was wondering if there is a way to simplify it. Here is the number of "slanted" squares:



where and are positive integers. This can be rewritten as




And of couse the number of nonslanted squares is

[digger]

Let (a,b) be left-lower vertex and (c,d) be opposite right-upper vertex.
Then we have to find the number of (a,b,c,d) with property and
This is the problem?
If yes then its simple. Choose pair (a, c) and independently (b, d).
So the answer is

P.S. I think my guess was right because the problem became trivial in case we consider rectangles (a,b,c,d) and (a+h,b+h,c+h,d+h) be the same. Then we simply move and so have distinct rectangles.

[drunner2007]

digger wrote:

Let (a,b) be left-lower vertex and (c,d) be opposite right-upper vertex.
Then we have to find the number of (a,b,c,d) with property and
This is the problem?
If yes then its simple. Choose pair (a, c) and independently (b, d).
So the answer is

P.S. I think my guess was right because the problem became trivial in case we consider rectangles (a,b,c,d) and (a+h,b+h,c+h,d+h) be the same. Then we simply move and so have distinct rectangles.

We are looking for squares, not just rectangles. I'm not sure that the result works. For example, with m=4 and n=5 we have 10 slanted squares and 20 nonslanted squares. You're expression gives 60.

[Altheman]

Can a recursion be useful for the slanted squares? [ex. when m=n] You can have a_{n+1}=4a_n+b_n where b_n denotes the number of squares that where x (or y) component has a distance of n+1

[JBL]

When , see http://www.research.att.com/~njas/sequences/A002415

For rectangles when , see http://www.research.att.com/~njas/sequences/A085582

[Altheman]

Say that the m=n is sequence 1, then the link says that it is equal to seq2+seq3

they give you seq2, but then they say that seq3=seq1-seq2

That is such bs. haha

[4everwise]

Here's an idea for the horizontal ones:

WLOG, say Then you can pick the size of the square (and location on the "m axis") in ways.

Then, you need only select a starting point along the "n axis." This can be done in ways, so for the total, just multiply the two together.

I think...

[TZF]

The Key

The four vertexes of any square can be described as being points on a larger square which is parallel to the grid lines.

Turning the Key

Consider square ABCD (labeled counterclockwise), with sides parallel to the gridlines, and k dots on each side, inclusive of vertexes. Suppose we start with vertex A, and, moving counterclockwise, mark every (k-1)th point, until we return to A. These points happen to be B, C, and D, and together form the whole square.

Instead if we move one point counterclockwise of A and repeat the procedure, we will find that these four vertexes form a different square. We can repeat this for the rest of the points on AB, and each will define a different square. Hence, there are k-1 squares formed by a k by k root square whose sides parallel to the gridlines (we're subtracting one because we don't want to count both vertexes as starting points).

Opening the Door

Now, all that is left is to calculate the number of k by k point squares (|| to axes) there are in an m by n lattice.
This is simply (m-k+1)(n-k+1).

Each of these squares is actually the root square of (k-1) different squares.
So, for each k, there are (m-k+1)(n-k+1)(k-1) different squares.

Now, WLOG say .

Then,

, which can easily be broken down with the sum of squares and sum of cubes formula.

It simplifies to , where

Or, if you prefer, the somewhat cleaner:

[Altheman]

err...how can that be correct if it is not symmetric in and ?

[cincodemayo5590]

Altheman wrote:

err...how can that be correct if it is not symmetric in and ?

The Zuton Force wrote:

Now, WLOG say .

[t0rajir0u]

(Edited.) Misread, sorry.

[Altheman]

Okay I think I will finally read the posts and offer a solution. Zuton Force had a great idea!

In essence, for each square, we can construct another square by drawing lines parallel to the coordinate axes through the verticies.

Suppose our squares are circumscribed by a by square, then we have: border points on the square, and a forth of these determine a square, for a total of squares.

Now lets consider a by square. [WLOG ] The largest square that we can have is by . Suppose we have a by square. We have by squares that are parallel to our axes.

Hence, we want the sum: .

Which I just plugged into my calculator [this is trivial...sum of cubes, squares, etc]

Then I factored on my calculator.



[which is obviously positive since .]

[Did I do anything wrong? Does this work for small values? I feel like we should not be able to solve something that was not solved on the OEIS.]

[TZF]

Well your result seems to agree with mine (you interchanged and and replaced with , or something like that - most likely, you used side-lengths and I used lattice points - you might want to clarify this), and your approach was pretty much what I did.

So I'm assuming you got what I did, which works for every example I bothered to try.

I can't believe that OEIS wouldn't have it...


Anyway, I'm after a combinatorics oriented solution. I can see why there might be a is coming from (in my version of the formula).

To choose the root squares setting the coordinate of the lower-left corner to means we need to pick 2 points of the .
To choose a slanted square originating from such a root square, we need to choose 3 points from : the bounds of the root square and the seed point in between from which we will count off and get the other vertexes.

And then, adding them, .

However, I can't figure out how to complete the proof with this approach - can anyone help? Or offer a different combinatorics solution?

[JBL]

Altheman wrote:

[Did I do anything wrong? Does this work for small values? I feel like we should not be able to solve something that was not solved on the OEIS.]

The Zuton Force wrote:

I can't believe that OEIS wouldn't have it...

I've tried all of the standard input forms that I would expect (as a triangle by rows, as a square array by diagonals) and wasn't able to find it, so it seems it's just not there. It's actually not that shocking -- there are lots and lots of integer sequences out there
I've submitted it now, including a link back to this thread -- my past experience is that it takes a few days to a week for a submission to show up online. I'll probably make another post on this thread when it does appear. (I submitted it in Altheman's form because the only difference is that TZF's has a lot of zeroes.)

[JBL]

This now exists in the OEIS: http://www.research.att.com/~njas/sequences/A130684