login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000938 Number of collinear point-triples in an n X n grid.
(Formerly M4527 N1919)
47

%I M4527 N1919

%S 0,8,44,152,372,824,1544,2712,4448,6992,10332,15072,21012,28688,38520,

%T 50880,65480,83640,104676,130264,160556,195848,235600,282840,336384,

%U 397136,465876,544464,630684,729744,837744,958384,1091904,1238520,1400140,1581384,1776084

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

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

%D 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.

%D R. K. Guy, Unsolved combinatorial problems, pp. 121-127 of D. J. A. Welsh, editor, Combinatorial Mathematics and Its Applications. Academic Press, NY, 1971.

%D 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.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H R. H. Hardin and Alois P. Heinz, <a href="/A000938/b000938.txt">Table of n, a(n) for n = 2..1000</a> (terms n=2..59 from R. H. Hardin)

%H R. K. Guy and P. A. Kelly, <a href="/A000755/a000755_1.pdf">The No-Three-Line Problem</a>, Research Paper 33, Department of Mathematics, Univ. of Calgary, Calgary, Alberta, 1968. [Annotated scanned copy]

%H R. K. Guy and P. A. Kelly, <a href="/A000755/a000755_2.pdf">The No-Three-Line Problem</a>, condensed version in Canad. Math. Bull. Vol. 11, pp. 527-531, 1968. [Annotated scanned copy]

%H R. K. Guy, P. A. Kelly, N. J. A. Sloane, <a href="/A000755/a000755.pdf">Correspondence, 1968-1971</a>

%F 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

%F a(n) = binomial(n^2, 3) - A045996(n). - _Ignacio Larrosa Cañestro_, May 23 2010

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

%p 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;

%p seq(a(n),n=2..30); # _Dennis P. Walsh_, Mar 02 2013

%t 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_ *)

%Y Cf. A000769, A272651.

%Y Cf. A157882 for the 3-D version.

%K nonn,nice

%O 2,2

%A _N. J. A. Sloane_

%E Terms a(11) through a(30) from _John W. Layman_, Sep 21 2000

%E Typo in formula corrected by _David Bevan_, Jan 09 2012

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 16 20:45 EST 2019. Contains 320189 sequences. (Running on oeis4.)