0
$\begingroup$

Consider an $(n+1)\times (n+1)$ grid of lattice points in the plane.

$A(n):$ # of squares with vertices on the grid.

It's relatively well-known that $A(n)=\frac{n(n+1)^2(n+2)}{12}$. Now, $A(n) = B(n) + C(n)$ . Where $B(n) = \frac{n(n+1)(2n+1)}{6}$ is the number of "orthogonal" squares. Meaning that the sides are parallel to borders of original square.

$C(n):$ # of "slanted" squares.

$C(n) = D(n) + E(n)$ . Where,

$D(n):$ # of squares intersecting the sides of unit squares.

$E(n):$ # of squares non-intersecting the sides of unit squares.

My question is to find a closed formula for $E(n)$.

Note that $D(n) + E(n) = \frac{n^4 - n^2}{12}$. Hence $$ D(1) = 0, D(2) = 0, D(3) = 2, D(4) = 10, D(5) = 30, D(6) = 73, D(7) = 148\\ E(1) = 0, E(2) = 1, E(3) = 4, E(4) = 10, E(5) = 20, E(6) = 32, E(7) = 48 $$ Maybe $E(n) = A008050$ in OEIS.

Thanks in advance.

Improve this question
$\endgroup$
7
  • $\begingroup$ I don't mean to be rude, but what is your question? Your post looks like a statement. Do you mean to ask if $E(n)$ is given by A008050 in OEIS? Also, do you have a reason to believe that this is the case, other than having the first few numbers correct? $\endgroup$
    – Joonas Ilmavirta
    Commented Feb 11, 2015 at 19:09
  • $\begingroup$ My question is to find a closed formula for $E(n)$. (in bold). I'm not sure that coincide with A008050, the only evidence are the first few values. $\endgroup$
    – user66997
    Commented Feb 11, 2015 at 19:20
  • 1
    $\begingroup$ In that case, please edit your question to make it clear what you are asking and what are your own thoughts. It didn't even cross my mind that you were after a formula for $E(n)$. The meaning of the word "find" is a bit unclear. By the way, are you familiar with the site math.stackexchange.com and the difference between it and MathOverflow? $\endgroup$
    – Joonas Ilmavirta
    Commented Feb 11, 2015 at 19:25
  • 1
    $\begingroup$ Is it not the case that the squares counted by $E(n)$ are precisely the squares rotated $\pi/4$ from the orthogonal? If so, they should be fairly easy to count and I'd think it wouldn't be hard to find a formula. $\endgroup$
    – Gerry Myerson
    Commented Feb 11, 2015 at 23:02
  • 1
    $\begingroup$ Yes, and the sides of those squares are rotated through $\pi/4$ with respect to the borders of the original square. Aren't all of the $E(n)$ squares like that? $\endgroup$
    – Gerry Myerson
    Commented Feb 11, 2015 at 23:17

1 Answer 1

Reset to default
1
$\begingroup$

It is not clear to me what you mean by intersecting the sides of unit squares but based on your comment I think it is just what Gerry says: Your grid makes up $n^2$ unit squares and $E(n)$ counts the squares of side $\sqrt{2}, 2\sqrt{2}, 3\sqrt{2}, ... , \lfloor\frac{n}{2}\rfloor\sqrt{2}$ whose sides have slope $\pm 1.$ The number of these is $(n-1)^2+(n-3)^2+\cdots$ which agrees with $3^2+1^2=10=E(4)$ and $4^2+2^2=20=E(5)$ but would suggest $5^2+3^2+1^2=35$ for $E(6).$ Are you sure your counts are correct? If it is what Gerry says then $E(n)=\frac{(n-1)n(n+1)}{6}.$

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes, that's the answer. $E(6)$ and $E(7)$ must be fixed. We have $E(n) = \sum_{k=1}^{\lfloor\frac{n}{2}\rfloor}(n+1-2k)^2 = \frac{(n-1)n(n+1)}{6}$. $\endgroup$
    – user66997
    Commented Feb 12, 2015 at 1:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .