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

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

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)
45
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

2,2

COMMENTS

This is 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

R. H. Hardin, Table of n, a(n) for n=2..59, May 22 2010

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

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

Cf. A000769. [From R. J. Mathar, May 21 2010]

Cf. A157882 for the 3-D version.

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

Sequence in context: A188148 A100583 A036464 * A165618 A059596 A181358

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

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified April 20 04:30 EDT 2014. Contains 240779 sequences.