[seqfan] Re: Squares in a grid
franktaw at netscape.net
franktaw at netscape.net
Sat Mar 7 11:54:06 CET 2009
I agree with everything you wrote.
"Distinct up to translation" means what you think it means. Thus, the
comment in A024206 is wrong and should be corrected. Another way
to say this is that we are looking for squares equivalent up to
translation,
reflection, and rotation of the (infinite) grid; the rotation taking
the
side of length 5 orthogonally to the 3/4/5 side does not preserve the
grid. (This still leaves the comment in A024206 wrong, not just
misinterpreted.)
The sequence matching the comment in A024206 is in fact the triangular
numbers (offset by one: A000217(n-1) = C(n,2) = n(n-1)/2). All that
matters for this is the ordered pair of numbers representing the change
in the x and y coordinates; choosing the side to be counted uniquely,
these must be 0 <= y, 1 <= x, with x + y < n. There are n-1 of these
summing to n-1 -- (1,n-2); (2,n-1); ...; (n-1,0) -- so the total number
is
C(n,2).
It is easy enough to see that this is equivalent to the corrected
property
for A024206; each square occurs twice under reflection except those
where the sides are either parallel to or at a 45 degree angle to the
grid;
the numbers of these are given by A032766 (shifted right), so we have
A000217(n-1) = 2*A024206(n) - A032766(n-1)
and the (rational) generating functions will then match.
Franklin T. Adams-Watters
-----Original Message-----
From: Joshua Zucker <joshua.zucker at gmail.com>
I was reading the entries for A002415 and its friends, and I just
can't figure out http://www.research.att.com/~njas/sequences/A024206 .
What exactly does "distinct up to translation" mean? Looking at
http://www.research.att.com/~njas/sequences/a2415.gif I think that
a(4) should be 6, not 5, since there's the 1x1, 2x2, 3x3, the diagonal
sqrt(2), and the two mirror-symmetric ones with sqrt(5) as one of the
vectors. I suppose those are not considered "unique up to
translation" but then I don't see the difference between this sequence
and A108279. What makes these two sequences different? I'm kinda
thinking that the sequence differs from A108279 because the square
with side length 5 parallel to the axes is considered different from
the square with side length 5 as the hypotenuse of a 3-4-5 triangle,
but then I don't know how to say what I mean there exactly.
Maybe what I'm thinking is
A002415: squares
A024206: squares, considered different if they are not translations OR
reflections in the coordinate axes (but rotations ARE considered
different?)
A108279: noncongruent squares
Any pointers on figuring this out would be much appreciated.
Even more appreciated would be some pointers about proofs that the
formulas for answering these square-counting problems are as
indicated, and also any nifty bijective proofs (combinatorial
arguments) that the various other things counted by these sequences
really are equal to each other.
Thanks!
More information about the SeqFan
mailing list