I need to count the number of triangles formed in a grid of $n\times n$ with positive integer coordinates $(0..n)$. For example for $n = 1$ the answer is 4.
triangles in a grid of $n\times n$ with positive coordinates
2
$\begingroup$
triangles
-
0$0$ isn't a positive integer! – 2012-05-31
-
1I think exact formula may be very hard. The problem is dealing with lines that pass through $3$ or more lattice points. This is sensitive to number-theoretic properties of $n$. – 2012-05-31
-
1Calculate it for some small values of $n$, and look it up in the Online Encyclopedia of Integer Sequences. – 2012-05-31
-
0@Qiaochu, I have read that in France, zero is considered to be positive. – 2012-05-31