I am interested in counting the number of triangles that can be constructed within a grid of points measuring $ n \times n $. The number of sets of 3 points that can be found when $ n \geq 3 $ is simply $ n^2 \choose 3 $. If the number of degenerate sets where the 3 points are collinear is found, the number of triangles can be found by subtracting the number of degenerate sets from the total number of sets.
However, I am running into some trouble counting these degenerate sets because in grids where $ n \geq 5 $ these degenerate sets can have gradients in the grid other than $ 1, 0 $ or $ \infty $ . For every second grid from $n=3$, a line with a higher gradient can be found in the grid. For example, when $n=5$ the gradients are ${0,1,\infty,2}$ and for $n=7$ the gradients are ${0,1,\infty,2,3}$. Note that the gradient of 2 can also be thought of as 0.5 as the grid can be rotated and lines are found in both directions. The number of degenerate sets with gradients of $1,0$ or $\infty$ is: $$2{n \choose 3}(n+1) + 4\sum_{r=3}^{n-1}{r \choose 3} $$ These degenerate sets are in every grid where $ n \geq 3$. Though for larger grids I am struggling to count the total number of degenerate sets. Does anyone have any ideas on how to do this?
Note that some work has previously been done on this for $ n = 5$ : How many triangles can be created from a grid of certain dimensions?
My working on $n=5$ goes like this:
The total number of 3 point sets: $${(5^2) \choose 3} = 2300$$
Degenerate sets with gradients of $1,0$ or $\infty$: $$2{5 \choose 3}(5+1) + 4\sum_{r=3}^{4}{r \choose 3} = 140 $$
Degenerate sets with gradients of $2$: $$12{3 \choose 3} = 12$$
Therefore, the total number of triangles is: $$2300 - (140 + 12) = 2148$$
This answer gives 6 less triangles than what the commenter almagest suggested, which leads me to think that he may not have considered the rotation of the degenerate lines with gradient 2. I can't be sure of this though. I need to write a brute force algorithm which can evaluate for various values of n to check my working and find a general trend.
