How many ways we can choose three points in a $n\cdot n$ grid?

283 Views Asked by At

We can calculate the number of square or rectangle in a $n\cdot n$ grid.

No of squares $=1^2+2^2+3^2+.....+(n-1)^2$

No of rectangles $=1^3+2^3+3^3+.....+(n-1)^3$

So what if we want to calculate the no of all possible quadrilateral? We can choose $4$ points out of $n^2$ points.But in that case, there will be many instances where $3$ or more points will be co-linear.So these will not be a true quadrilateral. So I need to find those combinations of $3$ or more points being co-linear?

References:

How many squares are in the chessboard?

Analysis of how-many-squares and rectangles are are there on a chess board?

2

There are 2 best solutions below

3
On

So what if we want to calculate the no of all possible quadrilateral ?

Consider $2\times 2$. Consider all possible quadrilateral shapes of specific areas and count the number of ways (by rotations and reflections). If I did not miss out any shape, here is what I got: enter image description here

0
On

This is not an answer, but the number of squares on a $n \times n$ grid is given by $n^2 (n^2 -1)/12$.

Assume $k$ (with $ 1 \leq k \leq n-1$) is the width (and height) of an arbitrary square measured along the $x$ and $y$ directions of a $n \times n$ grid. This tight ``bounding box'' can have $(n-k)^2$ different positions within that grid, whereas there are only $k$ such different squares in that box each with a different size and orientation. The total number of squares in the grid is therefor

$$\sum_{k=1}^{n-1} (n-k)^2 k = \frac{n^2(n^2-1)}{12}$$.