Combinatorial Proof for the Number of Squares in a Grid

Question

I am exploring combinatorial methods to solve a problem related to counting the number of squares in a grid. Given an 'a x b' grid of evenly spaced points, I want to understand how to determine the total number of squares that can be formed in the grid. I solved the problem with programming with basic loops, but was wondering if there is a more elegant math solution.

First example: 15 squares with a length of 1

Second example: 8 squares with a length of 2

Third case: 3 squares with a length of 3

So in this case the grid is a = 4, b = 6, 4x6 grid and the sum of all squares would be 26.

I would appreciate any insights, explanations, or resources on combinatorial methods for counting squares in such grids.

Answer 1

In your example, the $3x5$ grid provided $3 \times 5$ squares of size 2, $2 \times 4$ squares of size 2, and $1 \times 3$ squares of size 2.

There's 2 key observations to make:
(1) Given the smaller dimension of the grid ($n=3$), we can create squares up to size $3$.
(2) Given the dimensions of the grid ($a \times b$), the number of squares of size $n$ can be determined by $(a-n+1) \times (b-n+1)$.

This means that given a $a \times b$ grid, we can calculate the total number of squares as $$\sum_{i=1}^n (a-i+1) \times (b-i+1)$$ where $n = \min(a,b)$.

Answer 2

Write $f(a,b)$ for the number of (axes-aligned!) squares in an $a\times b$ grid. By symmetry, $f(b,a)=f(a,b)$, hence it suffices to compute $f(a,b)$ for the case that $b\ge a$. In that case, we note that $f(a,b+1)-f(a,b)$ does not depend on $b$: It is the number of squares with at least one (and hence exactly two) vertices in the last row. As there are $\binom a2$ ways to pick two out of $a$ vertices, we conclude that $f(a,b)$ is a linear function of $b$ (provided $b\ge a$), namely $$\tag1 f(a,b)=\binom a2b+c(a)$$ with an offset $c(a)$ that depends only on $a$. We find $c(a)$ by adjusting it so that $(1)$ gives the correct answer when $b=a$, i.e., for a square grid.

In an $a\times a$ grid, we find one square of side length $a-1$, four squares of side length $a-2$, and more generally $k^2$ squares of side length $a-k$ (as can be shown by checking which grid points can be the top left vertex of such a square). With the well-known formula for the sum of squares, this makes $$\tag2f(a,a)=1^2+2^2+3^3+\cdots +(a-1)^2=\frac{(a-1)a(2a-1)}6.$$ From $(2)$ and $(1)$, we quickly find $c(a)=\frac{a-a^3}6$, hence ultimately $$ f(a,b)=\frac{a(a-1)(3b-a-1)}6\qquad\text{if }b\ge a.$$