Squares in a grid

$\red{Note:}$ This is not my solution. You can check it out at here .

For the general case, let's assume that $2 ≤ n ≤ m$ .

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

$\displaystyle P(a) = (m - a) (n - a)$

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:

$\displaystyle a = dx + dy$

There are a possibilities to split each a into $dx$ and $dy$ as shown below (right). (Note that $dx \ne 0$ , 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 = 0$ .)

Possible bounding-box positions and possible squares in bounding box.

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:

$\displaystyle N = \sum_{a=1}^{n-1} a(m - a) (n - a) = \sum_{a=1}^{n-1} (a^3 - (m + n) a^2 + m n a)$

Using the well-known (or easily googleable) Faulhaber formulas , we get:

$\displaystyle N= \frac{1}{4} (n - 1)^2 n^2 - \frac{1}{6} n(n - 1) (2n - 1) (m + n) + \frac{1}{2} (n - 1) n^2 m$

and after a bit of rearranging and simplifying:

$\displaystyle N(n, m) = \frac{1}{12} n(n - 1) (n + 1) (2 m - n)$

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, n$ are the numbers of pegs along the edge as in the question. If we set $n = m = k + 1$ , we get:

$\displaystyle N(k) = \frac{1}{12} k (k + 1)^2 (k + 2)$