How many squares can you make with equal ranged points?

This question is directly related to How Many Squares on the Peg Solitaire.

Is it possible to formulate with a given dimension of equal ranged points $m\times n$ where $m,n\geqslant 2$?

For example;

$2\times2$ there is only $1$ square possible:

$3\times2$ there are only $2$ squares possible and $3\times3$ there are $6$ squares shown as below:

• Looks like something that's polynomial in two variables - if so, plugging in lots of small m and n would give you the answer – boboquack May 16 '17 at 9:11

For the general case, let's assume that 2 ≤ nm.

Every possible square has an axis-aligned boundary box that is a square of edge length a. Such a square can fit into the n × m grid at

P(a) = (ma) (na)

positions, see illustration below (left). If we define each square by the edge of its north-west corner (dx, dy), dx > 0, dy ≥ 0; the edge length of the bounding box is

a = dx + dy .

There are a possibilities to split each a into dx and dy as shown below (right). (Note that dx can't be zero, because such a square would be a 90° rotation of an axis-aligned square that has already been accounted for by the case where dy is zero.)

Possible edge lengths of bounding boxes are 0 < a < n. Therefore, the number of squares that fit into a grid of n × m nodes is:

N = ∑a a · (ma) (na);    a = 1,..., n − 1
= ∑a (a³ − (m + n) a² + m n a)

Using the well-known (i.e. easily googleable) Faulhaber formulas, we get:

N= ¹/₄ (n − 1)² n²   − ¹/₆ (n − 1) (n (2n − 1) (m + n)   + ¹/₂ (n − 1) n² m

and after a bit of rearranging and simplifying:

N(n, m) = ¹/₁₂ (n − 1) n (n + 1) (2 mn)

My approach is different from (and perhaps less elegant than) Wen1now's, but it arrives at the same solution. There's a difference in nomenclature; k is the edge length of the grid, m and n are the numbers of pegs along the edge as in the question. If we set n = m = k + 1, we get:

N(k) = ¹/₁₂ k (k + 1)² (k + 2)

• So what is the formula which is symmetric in n and m (recall that you assumed n<=m)? – Matsmath May 16 '17 at 13:00
• I assumed nm so that I didn't have to use min(n, m) when I determine the number of square positions and the upper bound for the sums. I don't know whether there really is a symmatric formula. – M Oehm May 16 '17 at 13:14
• In “k is the edgel length of the grid, m and n are the numbers of pegs along the adge” are edgel and adge technical terms, or typos? – James Waldby - jwpat7 May 16 '17 at 16:52
• No, they are typos, of course. It should be "edge" in both cases. As I get older, I get sloppier and sloppier at typing and it bugs me. – M Oehm May 16 '17 at 17:02
• Nice! This formula in m and n is really nice as well. – Wen1now May 17 '17 at 22:33

I will deal with the $n\times n$ case only

Summarising this :)

Let $T_n$ be the total number of squares (including tilted ones) on a square grid and let $N_n$ be the number of 'normal' squares, oriented such that the sides of these squares are parallel to the sides of the original grid. I claim that $T_n=T_{n-1}+N_n$ by providing a bijection between tilted squares in a $n\times n$ grid and all squares in a $(n-1)\times (n-1)$ grid. For any square in a $(n-1)\times (n-1)$ grid, fix the top right corner (top takes priority - so a diagonal square would just be the top corner) and move the vertex that is counterclockwise around from it down one unit. Then this forms a side of a new square (such that the top right vertex is still the top right vertex). This is non-trivially a bijection, but it is not that hard to prove either so I leave it as an exercise.

Bijection picture (appropriated from brilliant.org):

So since $N_n = \frac{n(n+1)(2n+1)}{6}$ (which can be found just about anywhere) we can sum the first $n$ things to find $T_n$. This turns out to be

$\frac{n(n+1)^2(n+2)}{12}$

I believe. We could check - base case n=1 both sides are equal.

Assume that it is equal for $n$. Then increasing by 1 gives

$\frac{n(n+1)^2(n+2)}{12} + \frac{2(n+1)(n+2)(2n+3)}{12}$, which, after some algebraic manipulation should yield $\frac{(n+1)(n+2)^2(n+3)}{12}$ which is what we wanted.

So the number of squares on a $n\times n$ grid is a neat

$\frac{n(n+1)^2(n+2)}{12} \square$

Mathematics can be so beautiful.