A000938 Number of collinear point-triples in an n X n grid. (Formerly M4527 N1919)

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,3

Comments

This is related to the no-3-in-line problem on an n X n 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

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

Example

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

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

Crossrefs

This is the main diagonal of the array in A334704.

Cf. A000769, A272651.

Cf. A157882 for the 3-D version.

Sequence in context: A100583 A261996 A036464 * A252871 A307044 A165618

Adjacent sequences: A000935 A000936 A000937 * A000939 A000940 A000941

Keyword

nonn,nice

Author

N. J. A. Sloane

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

Status

approved