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?
 A: 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.
A: 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.
