General form of amount of triangles that can be formed in an MxN point lattice - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T06:13:44Z http://mathoverflow.net/feeds/question/15331 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/15331/general-form-of-amount-of-triangles-that-can-be-formed-in-an-mxn-point-lattice General form of amount of triangles that can be formed in an MxN point lattice Manuel 2010-02-15T13:27:32Z 2010-02-24T08:23:17Z <p>I've been searching for the answer for many years, both by researching by myself and reading about the subject. Now I'm wondering if this has a solution.</p> <p>The problem can be stated as follows.</p> <p>Given a M x N grid of points, how many triangles with vertices in the grid can be formed? Note that you can't select two points that coincide or three collinear points because that wouldn't conform a triangle (area would be 0)</p> <p>OK, I know a bit of programming and could manage to code a program that solves this, but would REALLY like to know if there is a general form depending on M and N. I suspect it has to do with prime numbers... (Perhaps I totally missed heheh)</p> <p>Thanks for your time! Manuel</p> http://mathoverflow.net/questions/15331/general-form-of-amount-of-triangles-that-can-be-formed-in-an-mxn-point-lattice/15348#15348 Answer by HenrikRüping for General form of amount of triangles that can be formed in an MxN point lattice HenrikRüping 2010-02-15T17:26:42Z 2010-02-15T17:26:42Z <p>ok here is one answer, but I think, you already knew that:</p> <p>so there are $\left((M+1)(N+1)\atop 3\right)$ possible triangles an we have to subtract the number of triangles, which are degenerated. Every degenerated triangle is given by a choice of 2 points $P=(x,y),P'=(x',y')$ and a choice of a lattice point on the segment from $P$ to $P'$. Let $R:=gcd(x-x',y-y')$. There should be exactly $R+1$ points on that line, so we get at least a method, how a computer programme could compute that number. </p> http://mathoverflow.net/questions/15331/general-form-of-amount-of-triangles-that-can-be-formed-in-an-mxn-point-lattice/15384#15384 Answer by Gerry Myerson for General form of amount of triangles that can be formed in an MxN point lattice Gerry Myerson 2010-02-15T23:06:34Z 2010-02-24T08:23:17Z <p>For the NxN case, at least, there is a literature. An entry point is sequence <a href="http://www2.research.att.com/~njas/sequences/A000938" rel="nofollow">A000938</a> in the On-Line Encyclopedia of Integer Sequences. </p>