A045996 Number of triangles in an n X n grid (or geoplane).

0, 4, 76, 516, 2148, 6768, 17600, 40120, 82608, 157252, 280988, 477012, 775172, 1214768, 1844512, 2725000, 3930384, 5550844, 7692300, 10482124, 14066996, 18619128, 24337056, 31449200, 40212160, 50921316, 63907468, 79542108

Offset: 1

Author

Ignacio Larrosa Cañestro

Keywords

• nice
• nonn
• easy

Comments

The triangles must have nonzero area -- their vertices must not be collinear.

The degenerate (i.e., collinear) triangles are counted in A000938. The 1000-term b-file there could be used to produce a 1000-term b-file for the present sequence. - N. J. A. Sloane, Jun 19 2020

Examples

			a(2)=4 because 4 isosceles right triangles can be placed on a 2 X 2 grid.
		

Links

• Vaclav Kotesovec, Table of n, a(n) for n = 1..1000
• I. L. Canestro, Checkerboard, sci.math 22 Oct 2000 [broken link]
• I. L. Canestro, Checkerboard, sci.math 22 Oct 2000 [Cached copy]

Crossrefs

Cf. A000938.

Programs

Mathematica

a[n_] := ((n - 1)^2*n^2*(n + 1)^2)/6 - 2*Sum[(n - k + 1)*(n - l + 1)*GCD[k - 1, l - 1], {k, 2, n}, {l, 2, n}]; Array[a, 28] (* Robert G. Wilson v, May 23 2010 *)

Formula

a(n) = ((n-1)^2*n^2*(n+1)^2)/6 - 2*Sum_{m=2..n} Sum_{k=2..n} (n-k+1)*(n-m+1)*gcd(k-1, m-1).

a(n) = binomial(n^2,3) - A000938(n). - R. J. Mathar, May 21 2010