Suppose we are given an $m\times n$ rectangular grid of lattice points, such as
$S=\{(k,l): 0\le k\le n-1,\; 0\le l\le m-1, \;k,l\in\mathbb{Z}\}$, and we want to determine
the number of (nondegenerate) triangles all of whose vertices are contained in this set.
I believe that I can start with $\dbinom{mn}{3}$ and then have to subtract the number of sets of 3 vertices
which lie on a line, and that there are
$\displaystyle m\binom{n}{3}$ such triples which lie on a horizontal line
and $\displaystyle n\binom{m}{3}$ such triples which lie on a vertical line; but what I would like to find out is
how to systematically count all such triples which lie on a diagonal line.
Furthermore, is there a simple formula for this number in terms of $m$ and $n$?
(This question may have been asked before, but the closest question I could find was
How many triangles can be created from a grid of certain dimensions?)
Best Answer
The problem comes down to counting, for each $k\ge 2$, the lines intersecting an $m\times n$ grid in exactly $k$ points. (If a line contains $k$ grid points, that line contributes $\binom k3$ degenerate triangles to the count.) We will compute, for each $(m,n)$, the generating function for these lines, i.e. a polynomial in $t$ where, for $k\ge 2$, the coefficient of $t^k$ is the number of lines intersecting the grid in $k$ points. (We'll ensure we don't count any lines intersecting the grid in less than $2$ points.)
The horizontal and vertical lines contribute $n t^m$ and $m t^n$ respectively, assuming $m,n>1$. The lines of negative slope contribute the same amount as those of positive slope, so it suffices to compute the contribution from the latter. For any lattice point $(x,y)$ with $1\le x\le m$ and $1\le y\le n$, the number of grid points on the ray with slope $p/q$ ending at $(x,y)$ is $$\min(\lceil\frac xp\rceil,\lceil\frac yq\rceil).$$ Note that in order for that segment to have at least two gridpoints we would need to have $x>p$ and $y>q$. So, if we set $$f(m,n,p,q;t)=\sum_{x=p+1}^m\sum_{y=q+1}^n t^{\min(\lceil x/p\rceil,\lceil y/q\rceil},$$ then $f(m,n,p,q;t)-f(m-p,n-q,p,q;t)$ is the generating function for lines of slope $p/q$ according to the number of grid points they contain.
To get the generating function for all lines, we sum over relatively prime pairs $p$ and $q$, with $1\le p\le m$ and $1\le q\le n$, double the result, and add the contributions for horizontal and vertical lines:
$$g(m,n;t)=n t^m [m>1] + m t^n [n>1] + 2\sum_{\substack{p,q\\(p,q)=1}} f(m,n,p,q;t)-f(m-p,n-q,p,q;t).$$
To check the answer, and hopefully find references, we compute this for small values with $m=n$ (i.e. for square grids), evaluate at $t=1$ (which forgets the length information) and hope that the result shows up in the Sloane OEIS. We get:
$$\begin{array}{ccc} n & g(n,n;t) & g(n,n;1)\\ \hline 1 & 0 & 0\\ 2 & 6 t^2 & 6\\ 3 & 8 t^3+12 t^2 & 20\\ 4 & 10 t^4+4 t^3+48 t^2 & 62\\ 5 & 12 t^5+4 t^4+16 t^3+108 t^2 & 140 \\ 6 & 14 t^6+4 t^5+4 t^4+36 t^3+248 t^2 & 306 \\ 7 & 16 t^7+4 t^6+4 t^5+20 t^4+64 t^3+428 t^2 & 536\\ \end{array} $$
We're in luck! The sequence appears in OEIS as A018808, which includes some promising references. I note that the formulas given there have the form of summations (although with slightly lower complexity than the ones I've written down), so it's unlikely you'll get a closed form.
For completeness, the number of degenerate triples corresponding to the rows of the table are $0, 0, 8, 44, 152, 372, 824$; these are obtained by replacing $t^k$ by $\binom k3$.