Different squares on an n X n lattice

[Pfoertner, Hugo]

-----Original Message-----
From: David Wilson [mailto:davidwwilson at comcast.net] 
Sent: Tuesday, June 07, 2005 05:39
To: seqfan at ext.jussieu.fr
Subject: Re: Different squares on an n X n lattice


I get

1 3 5 8 11 15 18 23 28 33 38 45 51 58 65 73 80 89 97 107 116 126 134 146
158 169 180 192 204 218 228 243 257 270 285 302 316 331 346 364 379 397
414 433 451 468 484 505 523 544 563 584 603 625 646 669 691 713 733 759

This confirms all submitted results.  Essentially I computed

a(n) = |{ x^2+y^2 : 0 <= x <= y and x+y < n}| - 1.

This counts squares with vertices on the n x n grid, distinct up to length 
of side.

If instead, we compute

a(n) = |{ (x, y) : 0 <= x <= y and x+y < n}| - 1.

we get the sequence

1 3 5 8 11 15 19 24 29 35 41 48 55 63 71 80 89 99 109 120 131 143 155
168 181 195 209 224 239 255 271 288 305 323 341 360 379 399 419 440 461
483 505 528 551 575 599 624 649 675 701 728 755 783 811 840 869 899 929

This counts squares with vertices on the n x n grid, distinct up to 
translation.
The first sequence considers square with vector edge (0, 5) equivalent to 
one
with vector edge (3, 4), since both have side 5, whereas the later counts 
them
as distinct, since they are not translations of one another.  This accounts 
for the
discrepancy starting at a(8).

--------------------------------------------------------

David,

many thanks for checking and extending my submission. I assume that you will
submit the extension plus suggestions for a more concise description
avoiding the ambiguity that had led to the confusion between Rainer
Rosenthal's and my results.


The 2nd sequence given above  is already in the OEIS (plus initial terms):

Either
http://www.research.att.com/projects/OEIS?Anum=A024206
0,1,3,5,8,11,15,19,24,29,35,41,48,55,63,71,80,89,99,109,120, ....
Expansion of x^2*(1+x-x^2)/((1-x^2)*(1-x)^2).
Comments:  a(n+1) is the number of 2 X n binary matrices with no zero rows
or columns, up to row and column permutation

or
http://www.research.att.com/projects/OEIS?Anum=A078126
Signed:    -1,-1,0,1,3,5,8,11,15,19,24,29,35,41,48,55,63,71,80,89,99,
Negative determinant of n X n matrix M_{i,j)=1 if i=j or i+j=1 (mod 2).
Comments:  a(n) = A002620(n) - 1.

Both are variants of the monstruous
http://www.research.att.com/projects/OEIS?Anum=A002620
0,0,1,2,4,6,9,12,16,20,25,30,36,42,49,56,64,72,81,90,100,
Name:  Quarter-squares: floor(n/2)*ceiling(n/2). Equivalently, floor(n^2/4).

I have no idea where to put the information given above. Into A024206,
A078126 or into the already "overweight" A002620 ?

Best regards

Hugo Pfoertner