3
$\begingroup$

I need to find out the number of squares in $N\times M$ grid.

I came across this formula

$$S = \frac{1}{6}N(N+1)(3M-N+1)$$

But in my case the squares do not necessarily need to be aligned with the axes of the grid. How do I calculate the number in that case?

$\endgroup$
1
$\begingroup$

Let's have R rows and C columns of dots. We'll assume C >= R.

First count all the squares that are aligned with the axes:

number of 1x1 squares is (R-1)*(C-1)

number of 2x2 squares is (R-2)*(C-2)

... until we get to R-R (we assumed R was smaller).

Now count all the squares not aligned with the axes:

(this squares will be tilted around an inner point or a smaller square)

number of 1x1 squares is the number of inner points => (R-2)*(C-2), each one can be rotated in place in only one way.

2x2 squares = inner 1x1 squares => (R-3)*(C-3), each rotated in 2 ways

3x3 squares = inner 2x2 squares => (R-4)*(C-4), each rotated in 3 ways

... until we get to R-R

Writing the sum of both: $$\sum_{i=1}^{R} i(R-i)(C-i)$$

which equals: $\sum_{i=1}^{R} RCi - Ri^2 - Ci^2 + i^3$

= RC$\sum_{i=1}^{R}i$ - (R+C)$\sum_{i=1}^{R}i^{2}$ + $\sum_{i=1}^{R}i^{3}$

= $RC\frac{1}{2} R(R+1) - (R+C)\frac{1}{6}R(R+1)(2R+1) + \frac{1}{4}R^{2}(R+1)^{2}$

= $\frac{1}{12}(R-1)R(R+1)(2C-R)$

This formula solves the Google Kickstart problem of Square Counting.

$\endgroup$
0
$\begingroup$

We are talking about the lattice points in the rectangle $R:=[0,n]\times[0,m]$, whereby we assume $1\leq m\leq n$. An axis-aligned lattice square $Q_0\subset R$ has side length $s\in[1,m]$. It can assume $m+1-s\geq1$ positions vertically and $n+1-s$ positions horizontally. Now such a $Q_0$ is in fact carrier of exactly $s$ lattice squares $Q_k$ $(0\leq k\leq s-1)$ inscribed in $Q_0$. These $Q_k$ have vertices on the sides of $Q_0$, but translated "counterclockwise" by $k$ from the vertices of $Q_0$. All these $Q_k$ have the same mobility in $R$, as has $Q_0$. Conversely: Any lattice square $Q\subset R$ is such a $Q_k$ for some $s$ and some $k$. It follows that the total number of lattice squares $Q\subset R$ is given by $$\eqalign{N&=\sum_{s=1}^m s (m+1-s)(n+1-s)\cr &={1\over12}m(m+1)(2mn+4n+2-m^2-m)\ .\cr}$$ Since Blix's $R=m+1$, $C=n+1$ this coincides with the old result.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.