# Counting squares in a part of a graph. What is the correct answer?

Consider the following set of points in the $$x - y$$ plane: $$A = \{(a,\ b)\ |\ a,\ b\in \mathbb{Z}, \ 1\leqslant a\leqslant9\quad \text{and} \quad 1\leqslant b\leqslant 5\}.$$ Find the number of squares whose vertices are points in $$A$$.

I reached an answer but don't know if it's right or not. (The source doesn't give the answer)

This reflects the essence of the approach.

First, we draw the blue line and choose any $$2$$ points on it and that will trace a square. The picture depicts $$2$$ cases. (The squares on the blue line)
Continuing this and advancing rightwards with every line before we reach the final yellow line, where one choice of points is absurd, because that square should go outside the figure itself. So, we have $$6$$ lines $$5$$ points long with one choice of points absurd so we need to exclude it.

After the $$6\cdot\binom{5}{2} - 1$$ squares we have, we only have to count squares in the last $$3$$ columns of points. Working on with the exact same reason and we have the lines in green, again with one choice of points absurd. So, there are $$4\cdot\binom{3}{2}-1$$ squares, totaling $$6\cdot\binom{5}{2} + 4\cdot\binom{3}{2} - 2\ \text{squares} = 70\ \text{squares}$$ but I doubt the number is too small.

What is the correct answer? How can it be reached? What will be the answer for the case when $$0\leqslant a\leqslant9\ \text{and} \ 0\leqslant b\leqslant 5$$? Thanks!

• @JeanMarie That shows the number of squares in $n\times n$ grid. But my one is $9\times 5$! Mar 5, 2021 at 9:29
• quora.com/Consider-it-as-an-N*M-Grid-Can-you-find-a-formula-to-find-the-number-of-squares# Mar 5, 2021 at 9:33
• Do squares with non axially parallel sides count, like this one: i.stack.imgur.com/T5UHZ.png ? Mar 5, 2021 at 9:36
• @hgmath Ah yes, I missed. Mar 5, 2021 at 9:37
• Is it $0\leq a\leq9$ or $1\leq a\leq9$, and similarly for $b$? Mar 6, 2021 at 15:38

I'm assuming the large rectangle as $$R:=[0,n]\times[0,m]$$ with $$n\geq m\geq1$$.

An axis-aligned lattice square $$Q_r$$ with side length $$r\in\{1,2,\ldots,m\}$$ has a certain mobility in $$R$$: It can be translated horizontally and vertically by integer amounts. It is easy to see that this $$Q_r$$ can be legally placed at $$(n+1-r)(m+1-r)$$ places as a lattice square in $$R$$.

Now such a $$Q_r$$ is in fact "housing" exactly $$r$$ lattice squares that have exactly the same mobility in $$R$$ as $$Q_r$$ has:

It follows that the total number of lattice squares that can be embedded in $$R$$ is given by $$N=\sum_{r=1}^m r(n+1-r)(m+1-r)={m(m+1)(2nm+4n+2-m^2-m)\over12}\ ,$$ whereby the sum could be computed using the formulas for $$\sum_{r=1}^m r^j$$ $$(0\leq j\leq3)$$.

Consiser which points can be as the lower left corner of those squares then: Squares with Size 0:$$9×5=45$$ Size1: $$8×4=32$$

Size 2: $$7×3=21$$

Size 3: $$6×2=12$$

Size 4: $$5×1=5$$

• Your way is right for the way I thought it, but as @hgmath commented squares with non-axially parallel sides count. Mar 5, 2021 at 9:41