A000755 -id:A000755 - cp's OEIS frontend

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

N. J. A. Sloane

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

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

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

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

This is the main diagonal of the array in A334704.
Cf. A000769, A272651.
Cf. A157882 for the 3-D version.

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

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

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

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

A000769 No-3-in-line problem: number of inequivalent ways of placing 2n points on an n X n grid so that no 3 are in a line.

Original entry on oeis.org

0, 1, 1, 4, 5, 11, 22, 57, 51, 156, 158, 566, 499, 1366, 3978, 5900, 7094, 19204

Offset: 1

N. J. A. Sloane

This means no three points on any line, not just lines in the X or Y directions.
A000755 gives the total number of solutions (as opposed to the number of equivalence classes).
It is conjectured that a(n)=0 for all sufficiently large n.
Flammenkamp's web site reports that at least one solution is known for all n <= 46 and n=48, 50, 52.
From R. K. Guy, Oct 22 2004: (Start)
I got the no-three-in-line problem from Heilbronn over 50 years ago. See Section F4 in UPINT.
In Canad. Math. Bull. 11 (1968) 527-531, MR 39 #129, Guy & Kelly conjecture that, for large n, at most (c + eps)*n points can be selected, where 3*c^3 = 2*Pi^2, i.e., c ~ 1.87.
As recently as last March, Gabor Ellmann pointed out an error in our heuristic reasoning, which, when corrected, gives 3*c^2 = Pi^2, or c ~ 1.813799. (End)

			a(3) = 1:
  X X o
  X o X
  o X X

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. B. Anderson, Journal of Combinatorial Theory Series A, V.27/1979 pp. 365 - 366.
D. Craggs and R. Hughes-Jones, Journal of Combinatorial Theory Series A, V. 20/1976 pp. 363-364.
H. E. Dudeney, Amusements in Mathematics, Nelson, Edinburgh 1917, pp. 94, 222.
M. Gardner, Scientific American V236 / March 1977, pp. 139-140.
M. Gardner, Penrose Tiles to Trapdoor Ciphers. Freeman, NY, 1989, p. 69.
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, Unsolved Problems Number Theory, Section F4.
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.
R. R. Hall, T. H. Jackson, A. Sudberry and K. Wild, Journal of Combinatorial Theory Series A, V.18/1975 pp. 336-341.
H. Harborth, P. Oertel and T. Prellberg, Discrete Math. V73/1988 pp. 89-90.
T. Kløve, Journal of Combinatorial Theory Series A, V.24/1978 pp. 126-127.
T. Kløve, Journal of Combinatorial Theory Series A, V.26/1979 pp. 82-83.
K. F. Roth, Journal London Math. Society V.26 / 1951, p. 204.
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).

Benjamin Chaffin, No-Three-In-Line Problem.
Alec S. Cooper, Oleg Pikhurko, John R. Schmitt and Gregory S. Warrington, Martin Gardner's minimum no-3-in-a-line problem, arXiv:1206.5350 [math.CO]. Also Amer. Math. Monthly, 121 (2014), 213-221.
Achim Flammenkamp, Progress in the no-three-in-line problem.
Achim Flammenkamp, Solutions of the no-three-in-line problem.
Achim Flammenkamp, Progress in the no-three-in-line problem, J. Combinat. Theory A 60 (1992), 305-311.
Achim Flammenkamp, Progress in the no-three-in-line problem. II, J. Combin. Theory Ser. A 81 (1998), no. 1, 108-113.
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.
S. V. Ullas Chandran, Sandi Klavžar, and James Tuite, The General Position Problem: A Survey, arXiv:2501.19385 [math.CO], 2025. See p. 4.
Eric Weisstein's World of Mathematics, Point Lattice.
Eric Weisstein's World of Mathematics, No-Three-in-a-Line-Problem.

Cf. A000755, A000938, A037185, A037186, A037187, A037188, A037189, A047840, A212807, A235453.
See A272651 for the maximal number of no-3-in-line points on an n X n grid, and A277433 for minimal saturated.
Cf. A194136 (triangular grid), A280537 (3D grid, no 4 in plane).

a(17) and a(18) from Benjamin Chaffin, Apr 05 2006
Minor edits from N. J. A. Sloane, May 25 2010
Edited by N. J. A. Sloane, Mar 19 2013 at the suggestion of Dominique Bernardi

A187062 Expansion of 2x^2 (4 +7x +5x^2 -x^3 -4x^4 +6x^6 +4x^7 -x^8 -2x^9) / ((1+x)^2 (1+x+x^2)^2 (1-x)^4) .

Original entry on oeis.org

0, 0, 8, 14, 26, 42, 64, 90, 134, 172, 232, 300, 378, 464, 584, 690, 834, 990, 1160, 1342, 1574, 1784, 2048, 2328, 2626, 2940, 3320, 3670, 4090, 4530, 4992, 5474, 6038, 6564, 7176, 7812, 8474, 9160, 9944, 10682, 11522, 12390, 13288, 14214

Offset: 1

Sean A. Irvine, Mar 21 2011

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (0,2,2,-1,-4,-1,2,2,0,-1).

Cf. A000755, A178465, A187397, A225606.

CoefficientList[Series[ 2x^2 (4 + 7x + 5x^2 - x^3 - 4x^4 + 6x^6 + 4x^7 - x^8 - 2x^9)/((1 + x)^2 (1 + x + x^2)^2 (x - 1)^4), {x, 0, 43}], x]  (* or *) LinearRecurrence[ {0, 2, 2, -1, -4, -1, 2, 2, 0, -1}, {8, 14, 26, 42, 64, 90, 134, 172, 232, 300}, 42] (* Robert G. Wilson v, Feb 17 2014 *)

a(n) = 2*a(n-2) + 2*a(n-3) - a(n-4) - 4*a(n-5) - a(n-6) + 2*a(n-7) + 2*a(n-8) - a(n-10) .

Name replaced by L. Edson Jeffery's definition. R. J. Mathar, Aug 06 2013

A213222 Minimum number of distinct slopes formed by n noncollinear points in the plane.

Original entry on oeis.org

3, 4, 4, 6, 6, 8, 8, 10, 10, 12, 12, 14, 14, 16, 16, 18, 18, 20, 20, 22, 22, 24, 24, 26, 26, 28, 28, 30, 30, 32, 32, 34, 34, 36, 36, 38, 38, 40, 40, 42, 42, 44, 44, 46, 46, 48, 48, 50, 50, 52, 52, 54, 54, 56, 56, 58, 58, 60, 60, 62, 62, 64, 64, 66, 66, 68, 68, 70, 70, 72, 72, 74, 74, 76, 76, 78, 78, 80, 80, 82, 82, 84

Offset: 3

Charles R Greathouse IV, Mar 02 2013

Scott formulated the problem (on the basis of a similar problem of Erdős), gave bounds, and conjectured the formula which Unger later proved.

Also the edge chromatic number of the n-polygon diagonal intersection graph. - Eric W. Weisstein, Mar 23 2018

Martin Aigner and Gunter M. Ziegler, Proofs from THE BOOK, Second Edition, Springer-Verlag, Berlin, 2000. Chapter 10.

Vincenzo Librandi, Table of n, a(n) for n = 3..1000
J. E. Goodman and R. Pollack, On the combinatorial classification of nondegenerate configurations in the plane, J. Combin. Theory Ser. A, 29 (1980), pp. 220-235.
Giovanni Resta, Illustration of terms a(3)-a(7)
P. R. Scott, On the sets of directions determined by n points, The American Mathematical Monthly 77:5 (1970), pp. 502-505.
Peter Ungar, 2N noncollinear points determine at least 2N directions, Journal of Combinatorial Theory, Series A, 33:3 (1982), pp. 343-347.
Eric Weisstein's World of Mathematics, Edge Chromatic Number
Eric Weisstein's World of Mathematics, Polygon Diagonal Intersection Graph
Index entries for linear recurrences with constant coefficients, signature (1,1,-1).

Cf. A000769, A000755, A219760.

Cf. A000217 (maximum number of slopes, with offset 1).

[2*Floor(n/2): n in [3..100]]; // Vincenzo Librandi, Mar 29 2014

A213222:=n->`if`(n = 3, 3, 2*floor(n/2)); seq(A213222(n), n=3..100); # Wesley Ivan Hurt, Mar 28 2014

CoefficientList[Series[(3 + x - 3 x^2 + x^3)/((1 + x) (1 - x)^2), {x, 0, 100}], x] (* Vincenzo Librandi, Mar 29 2014 *)
LinearRecurrence[{1,1,-1},{3,4,4,6},100] (* Harvey P. Dale, Dec 29 2024 *)

PARI
```
a(n)=if(n>3,n\2*2,3)
```

a(n) = 2*floor(n/2) for n > 3.

G.f.: x^3*(3+x-3*x^2+x^3)/((1+x)*(1-x)^2). [Bruno Berselli, Mar 04 2013]

A037185 Number of ways of placing 2n points on n X n grid so no 3 are in a line (solutions with no symmetry).

Original entry on oeis.org

0, 0, 0, 0, 3, 4, 11, 40, 41, 132, 122, 524, 407, 1284, 3681, 5683, 6800, 18853

Offset: 1

N. J. A. Sloane

Benjamin Chaffin, No-Three-In-Line Problem.
A. Flammenkamp, Solutions of the no-three-in-line problem
A. Flammenkamp, Solutions of the no-three-in-line problem
A. Flammenkamp, Progress in the no-three-in-line problem, J. Combinat. Theory A 60 (1992), 305-311.
A. Flammenkamp, Progress in the no-three-in-line problem. II, J. Combin. Theory Ser. A 81 (1998), no. 1, 108-113.

Cf. A000769, A000755.

a(17) and a(18) from Benjamin Chaffin, Apr 05 2006

A365437 Number of ways of placing n non-attacking queens on an n X n board, with no three queens in a straight line.

Original entry on oeis.org

1, 1, 0, 0, 2, 0, 0, 0, 8, 32, 40, 96, 410, 1392, 4416, 18752, 71486, 235056, 1001972, 4285920, 21887710, 94619480, 422557444, 2101021824, 11943690634, 61113195600

Offset: 0

Don Knuth, Nov 07 2023

			For n=8, place queens for rows 1..8 into columns 3,6,8,2,4,1,7,5, i.e.,
.
  +-----------------+
  | . . Q . . . . . |
  | . . . . . Q . . |
  | . . . . . . . Q |
  | . Q . . . . . . |
  | . . . Q . . . . |
  | Q . . . . . . . |
  | . . . . . . Q . |
  | . . . . Q . . . |
  +-----------------+
.
and rotate and/or reflect to get the other seven ways.
.
(Note that solutions such as
.
  +-----------------+
  | . . Q . . . . . |
  | . . . . . Q . . |
  | . . . Q . . . . |
  | Q . . . . . . . |
  | . . . . . . . Q |
  | . . . . Q . . . |
  | . . . . . . Q . |
  | . Q . . . . . . |
  +-----------------+
.
do not count as the queens on rows 4, 6, and 7 are in a straight line.)

Donald E. Knuth, Constraint Satisfaction (volume 4, fascicle 7a of The Art of Computer Programming, in preparation).

Sam Loyd, A Crow Puzzle, in Brooklyn Daily Eagle, 20 December 1896, for the case n=8.
Mathematics Stack Exchange, Are there large n-queens solutions without 3-in-a-line? (2023).
Ho Boon Suan, The n queens problem with no three on a line, MathOverflow, Nov. 2023.
Wikipedia, No three in line problem.
Wikipedia, Eight Queens Puzzle, [Of the twelve fundamental solutions on the 8x8 chessboard, only "Solution 10" satisfies no three in a line. In "Solution 9" the queens on a5, e3 and g2 are in one line. - _Vaclav Kotesovec_, Nov 08 2023]

Cf. A000170, A000755.

a(21) from Martin Ehrenstein, Nov 08 2023
a(22) from Martin Ehrenstein, Nov 09 2023
a(23) from Martin Ehrenstein, Nov 10 2023
a(24) from Martin Ehrenstein, Nov 16 2023
a(25) from Martin Ehrenstein, May 02 2024

A379299 a(n) is the maximum number k such that every permutation of the integers mod n admits at least k collinear triples.

Original entry on oeis.org

0, 0, 1, 0, 2, 0, 3, 0, 5, 2, 5, 0, 6, 9, 6, 4, 8

Offset: 1

Joshua Cooper, Dec 20 2024

Three points (x_i,y_i), i=1,2,3, are collinear if x_1*(y_2-y_3) + x_2*(y_3-y_1) + x_3*(y_1-y_2) == 0 (mod n).

Exhaustive search in SageMath obtained the reported values from Cooper and Solymosi 2004, where the authors show that (n-1)/4 <= a(n) <= (n-1)/2 for every odd prime n. In Li 2008, the author shows that a(n) = (n-1)/2 for every odd prime n.

			a(5)=2 because the permutation (in one-line notation) 0,1,3,2,4 admits two collinear triples mod 5: {(0,0),(1,1),(4,4)} is on the line y=x and {(0,0),(3,2),(2,3)} is on the line y=4*x; and all other permutations admit at least 2 collinear triples.

Joshua Cooper and Jack Hyatt, Permutations minimizing the number of collinear triples, arXiv:2501.02331 [math.CO], 2025. See p. 7.
Joshua N. Cooper and József Solymosi, Collinear points in permutations, Ann. Comb. 9 (2005), no. 2, 169-175; preprint, arXiv:math/0408396 [math.CO], 2004.
Liangpan Li, Collinear triples in permutations, Innov. Incidence Geom. 8 (2008), 171--173; arXiv preprint, arXiv:0805.0410 [math.CO], 2008.

Cf. A272651, A000769, A000755, A000938.

a(n) = (n-1)/2 for odd primes n.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A000769 No-3-in-line problem: number of inequivalent ways of placing 2n points on an n X n grid so that no 3 are in a line.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A187062 Expansion of 2*x^2 *(4 +7*x +5*x^2 -x^3 -4*x^4 +6*x^6 +4*x^7 -x^8 -2*x^9) / ((1+x)^2 *(1+x+x^2)^2 *(1-x)^4) .

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A213222 Minimum number of distinct slopes formed by n noncollinear points in the plane.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A037185 Number of ways of placing 2n points on n X n grid so no 3 are in a line (solutions with no symmetry).

Views

Author

Keywords

Links

Crossrefs

Extensions

A365437 Number of ways of placing n non-attacking queens on an n X n board, with no three queens in a straight line.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Extensions

A379299 a(n) is the maximum number k such that every permutation of the integers mod n admits at least k collinear triples.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A187062 Expansion of 2x^2 (4 +7x +5x^2 -x^3 -4x^4 +6x^6 +4x^7 -x^8 -2x^9) / ((1+x)^2 (1+x+x^2)^2 (1-x)^4) .