How many squares in the $m \times n$ grid
Is there a formula to evaluate the number of all squares in the $m \times n$ grid? Well, I'm just curious, I've seen the question like this somewhere at the university, to solve this they were dividing the grid with $m - 1$ and $n - 1$ lines...I don't know what's next.
$\endgroup$ 12 Answers
$\begingroup$Suppose $n\ge m$.
- Number of squares of size 1: $m\cdot n$
- Number of squares of size 2: $(m-1)\cdot (n-1)$
- ...
- Number of squares of size m: $1\cdot (n-m+1)$
Result: $$\begin{align} \sum_{k=1}^m k \cdot (n-m+k) & =(n-m)\sum_{k=1}^m k +\sum_{k=1}^m k^2 \\ & = (n-m) m(m+1)/2 + m(m+1)(2m+1)/6 \\ & = \frac{m(m+1) (3n-m+1)}{6}\end{align}$$
$\endgroup$ $\begingroup$Rectangles in rectangle $$\frac{(n^2+n)(m^2+m)}{4}$$
Rectangles in square $$\frac{(n^2+n)^2}{4}$$
Squares in rectangle $$m≥ n-1,\frac{(n^2+n)}{2}m-\frac{(n^3-n)}{6}$$
Squares in square $$\frac{(n^2+n)(2n+1)}{6}$$
$\endgroup$ 7
