A000938 Number of collinear point-triples in an n X n grid.

0, 0, 8, 44, 152, 372, 824, 1544, 2712, 4448, 6992, 10332, 15072, 21012, 28688, 38520, 50880, 65480, 83640, 104676, 130264, 160556, 195848, 235600, 282840, 336384, 397136, 465876, 544464, 630684, 729744, 837744, 958384, 1091904, 1238520, 1400140, 1581384, 1776084

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice

Comments

This is related to the no-3-in-line problem on an n X n grid.

Examples

			a(3) = 8: the 3 rows, 3 columns and 2 diagonals of a 3 X 3 grid.
		

References

• M. A. Adena, D. A. Holton and P. A. Kelly, Some thoughts on the no-three-in-line problem, pp. 6-17 of Combinatorial Mathematics (Proceedings 2nd Australian Conf.), Lect. Notes Math. 403, 1974.
• R. K. Guy, Unsolved combinatorial problems, pp. 121-127 of D. J. A. Welsh, editor, Combinatorial Mathematics and Its Applications. Academic Press, NY, 1971.
• R. K. Guy and P. A. Kelly, The No-Three-Line Problem. Research Paper 33, Department of Mathematics, Univ. of Calgary, Calgary, Alberta, 1968. Condensed version in Canad. Math. Bull. Vol. 11, pp. 527-531, 1968.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..1000 (Terms n=2..59 from R. H. Hardin)
• R. K. Guy and P. A. Kelly, The No-Three-Line Problem, Research Paper 33, Department of Mathematics, Univ. of Calgary, Calgary, Alberta, 1968. [Annotated scanned copy]
• R. K. Guy and P. A. Kelly, The No-Three-Line Problem, condensed version in Canad. Math. Bull. Vol. 11, pp. 527-531, 1968. [Annotated scanned copy]
• R. K. Guy, P. A. Kelly, N. J. A. Sloane, Correspondence, 1968-1971

Crossrefs

This is the main diagonal of the array in A334704.

Cf. A000769, A272651.

Cf. A157882 for the 3-D version.

Programs

Maple

a:=n->2*sum(sum((n - k + 1)*(n - m + 1)*igcd(k - 1, m - 1), k= 2.. n), m= 2.. n) - n^2*(n^2 - 1)/6;
seq(a(n),n=2..30); # Dennis P. Walsh, Mar 02 2013

Mathematica

a[n_] := 2*Sum[(n - k + 1)*(n - m + 1)*GCD[k - 1, m - 1], {m, 2, n}, {k, 2, n}] - n^2*((n^2 - 1)/6); Table[a[n], {n, 2, 30}] (* Jean-François Alcover, Jul 11 2012, after Ignacio Larrosa Cañestro *)

Formula

a(n) = 2*Sum(Sum((n - k + 1)*(n - m + 1)*gcd(k - 1, m - 1), k, 2, n), m, 2, n) - n^2(n^2 - 1)/6. - Ignacio Larrosa Cañestro, May 23 2010

a(n) = binomial(n^2, 3) - A045996(n). - Ignacio Larrosa Cañestro, May 23 2010

Extensions

Terms a(11) through a(30) from John W. Layman, Sep 21 2000

Typo in formula corrected by David Bevan, Jan 09 2012

Offset changed to 1 and initial 0 added. - N. J. A. Sloane, Jun 19 2020