# What is the number of squares in an $N\times M$ grid, if the squares don't have to be aligned with the grid's axes?

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?

• – symplectomorphic Mar 5 '17 at 5:58
• This question is from the Google Kickstart 2017 Round A problem Square Counting. This round seems to be held only on Sunday 5 March 2017, so it will remain locked for the remainder of the day. – user642796 Mar 5 '17 at 8:09

## 2 Answers

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.

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.