number of triangles determined by a rectangular grid

Question

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?)

Answer 1

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$.

Answer 2

Let's attack this problem from a different angle. Instead of looking for lines, let us note that if we wish to find all the lines we can simply look for all possible rectangles such that the lines which contain two opposite corners pass through at least one point on the interior. I claim that a $q \times r$ rectangle has diagonals which contain at least one interior point iff there exist 3 natural numbers, $x_0$, $y_0$, and $k$ such that $x_0$ and $y_0$ are relatively prime, $k\geq 2$, and $k(x_0,y_0)=(q,r)$. Proof:

Assume that $q \times r$ diagonal contains interior points. Then there exists an $(x,y) \in \mathbb{N}$ such that $x<q$, $y<r$, and $\frac{x}{y}=\frac{q}{r}$. Let $\frac{x}{y}=\frac{x_0}{y_0}$ where $x_0$ and $y_0$ are relatively prime. Then $k=\frac{q}{x_0}$. That's one direction.

Now, assume that such an $x_0,y_0,k$ exist but the diagonal line doesn't contain a point. Clearly, for all $g \in \mathbb{N}$, where $g<k$, $g(x_0,y_0)$ is both in the interior of the rectangle and a lattice point. $\square$

The whole point of this is to show that we are interested in finding all $(x_0,y_0)$ pairs such that $2x_0<m$ and $2y_0<n$. For each such $(x_0,y_0)$, we can find, we add the following number of coplanar triplets to our list:

$$\#(x_0,y_0)=(m-2x_0)(n-2y_0)$$ It's messy, I know, and I don't like it, but hey, I'm pretty sure this is the simplest it's going to get. If I'm right, then that answers your question in the negative. Please let me know if anything is unclear or if you spot any mistakes. Thanks, I enjoyed that question!