A272651 -id:A272651 - 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

A103517 Expansion of (1+2*x-x^2)/(1-x)^2.

Original entry on oeis.org

1, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126

Offset: 0

Paul Barry, Feb 09 2005

Row sums of A103516.
Also the number of maximal and maximum cliques in the (n+1) X (n+1) rook graph. - Eric W. Weisstein, Sep 14 2017
Also the number of maximal and maximum independent vertex sets in the (n+1) X (n+1) rook complement graph. - Eric W. Weisstein, Sep 14 2017

G. C. Greubel, Table of n, a(n) for n = 0..1000
Eric Weisstein's World of Mathematics, Maximal Clique
Eric Weisstein's World of Mathematics, Maximum Clique
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
Eric Weisstein's World of Mathematics, Maximum Independent Vertex Set
Eric Weisstein's World of Mathematics, Rook Complement Graph
Eric Weisstein's World of Mathematics, Rook Graph
Index entries for linear recurrences with constant coefficients, signature (2,-1).

Cf. A103516.
Essentially the same as A004277, A005843, A051755, and A076032. - R. J. Mathar, Jul 31 2010
Cf. A272651 (for which this sequence is a conjectured continuation for large n).

[1] cat [2*n+2 : n in [1..60]]; // Wesley Ivan Hurt, Dec 07 2016

a := n -> 2*(n + 1) - 0^n: seq(a(n), n = 0..62); # Peter Luschny, May 12 2023

CoefficientList[Series[(-z^2 + 2*z + 1)/(z - 1)^2, {z, 0, 100}], z] (* Vladimir Joseph Stephan Orlovsky, Jul 10 2011 *)
CoefficientList[Series[2/(x - 1)^2 - 1, {x, 0, 62}], x] (* Robert G. Wilson v, Jan 29 2015 *)
Join[{1}, 2 Range[2, 20]] (* Eric W. Weisstein, Sep 14 2017 *)
Join[{1}, LinearRecurrence[{2, -1}, {4, 6}, 20]] (* Eric W. Weisstein, Sep 14 2017 *)

a(n) = 2*n + 2 - 0^n.
a(n) = Sum_{k=0..n} 0^(k(n-k))*(n+1).
Equals binomial transform of [1, 3, -1, 1, -1, 1, ...]. - Gary W. Adamson, Apr 23 2008
a(n) = 2*a(n-1) - a(n-2) for n > 2. - Eric W. Weisstein, Sep 14 2017
G.f.: (1 + 2*x - x^2)/(-1 + x)^2. - Eric W. Weisstein, Sep 14 2017

A279445 Triangle read by rows: T(n, k) is the number of ways to place k points on an n X n square grid so that no more than 2 points are on a vertical or horizontal straight line.

Original entry on oeis.org

1, 1, 1, 4, 6, 4, 1, 1, 9, 36, 78, 90, 45, 6, 1, 16, 120, 528, 1428, 2304, 2040, 816, 90, 1, 25, 300, 2200, 10600, 34020, 71400, 93000, 67950, 22650, 2040, 1, 36, 630, 6900, 51525, 270720, 1005720, 2602800, 4531950, 4987800, 3110940, 888840, 67950, 1, 49, 1176, 17934

Offset: 1

Heinrich Ludwig, Dec 17 2016

Length of n-th row is A272651(n) + 1, where A272651(n) is the maximal number of points to be placed under the condition mentioned.
Rotations and reflections of placements are counted. If they are to be ignored, see A279453.
For condition "no more than 2 points on a straight line at any angle", see A194193 (but that one is read by antidiagonals).

			The table begins with T(1, 0):
1  1
1  4   6    4     1
1  9  36   78    90    45     6
1 16 120  528  1428  2304  2040   816    90
1 25 300 2200 10600 34020 71400 93000 67950 22650 2040
...
T(3, 2) = 36 because there are 36 ways to place 2 points on a 3 X 3 square grid so that no more than 2 points are on a vertical or horizontal straight line.

Heinrich Ludwig, Table of n, a(n) for n = 1..109

Row sums give A197458.
Columns 2..10: A000290, A083374, A279437, A279438, A279439, A279440, A279441, A279442, A279443.
Diagonal T(n, n) is A279444.
Cf. A279453, A194193.

A279453 Triangle read by rows: T(n, k) is the number of nonequivalent ways to place k points on an n X n square grid so that no more than 2 points are on a vertical or horizontal straight line.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 1, 3, 8, 14, 17, 9, 2, 1, 3, 21, 73, 202, 306, 285, 115, 20, 1, 6, 49, 301, 1397, 4361, 9110, 11810, 8679, 2929, 288, 1, 6, 93, 890, 6582, 34059, 126396, 326190, 568134, 624875, 390426, 111798, 8791, 1, 10, 171, 2321, 24185, 185181, 1055025

Offset: 1

Heinrich Ludwig, Dec 17 2016

Length of n-th row is A272651(n) + 1, where A272651(n) is the maximal number of points that can be placed under the condition mentioned.
Rotations and reflections of placements are not counted. If they are to be counted, see A279445.
For condition "no more than 2 points on a straight line at any angle", see A235453.

			The table begins with T(1, 0):
1 1
1 1  2   1    1
1 3  8  14   17    9    2
1 3 21  73  202  306  285   115   20
1 6 49 301 1397 4361 9110 11810 8679 2929 288
...
T(4, 3) = 73 because there are 73 nonequivalent ways to place 3 points on a 4 X 4 square grid so that no more than 2 points are on a vertical or horizontal straight line.

Heinrich Ludwig, Table of n, a(n) for n = 1..109

Row sums give A279454.
Columns 2..8: A008805, A014409, A279454, A279455, A279456, A279457, A279458.
Diagonal T(n, n) is A279452.
Cf. A279445, A235453.

A326478 a(n) = ndenominator(nBernoulli(n-1))/denominator(Bernoulli(n-1)).

Original entry on oeis.org

1, 1, 1, 4, 1, 6, 1, 8, 3, 10, 1, 12, 1, 14, 5, 16, 1, 18, 1, 20, 7, 22, 1, 24, 5, 26, 9, 28, 1, 30, 1, 32, 11, 34, 35, 36, 1, 38, 13, 40, 1, 42, 1, 44, 3, 46, 1, 48, 7, 50, 17, 52, 1, 54, 55, 56, 19, 58, 1, 60, 1, 62, 21, 64, 13, 66, 1, 68, 23, 70, 1, 72, 1

Offset: 1

Peter Luschny, Jul 16 2019

nonn

Empirical: a(2*n) = [x^n] x*(2/(x - 1)^2 - 1) for n >= 1, implying the conjecture that a(2*n) = A103517(n+1) and/or A272651(n).

Conjectural, the odd fixed points > 1 of this sequence are A121707; in other words, for n > 1, denominator(n*Bernoulli(n-1)) = denominator(Bernoulli(n-1)) <=> n | Sum_{k=1..n-1} k^(n-1). (See the conjectures of Thomas Ordowski in A121707.)

Michel Marcus, Table of n, a(n) for n = 1..10000

Cf. A326577, A326578, A103517, A272651, A027641/A027642 (Bernoulli), A121707.

A326478 := n -> n*denom(n*bernoulli(n-1))/denom(bernoulli(n-1)):
db := n -> denom(bernoulli(n)): nb := n -> numer(bernoulli(n)):
a := n -> n/igcd(n*nb(n-1), db(n-1)): seq(a(n), n=1..73);

a[n_] := Module[{b =  BernoulliB[n - 1]}, n * Denominator[n * b] / Denominator[b]]; Array[a, 100] (* Amiram Eldar, Apr 26 2024 *)

a(n) = n*denominator(n*bernfrac(n-1))/denominator(bernfrac(n-1)); \\ Michel Marcus, Jul 17 2019

a(prime(n)) = 1.

a(n) = n/gcd(n*N(n-1), D(n-1)), with N(k)/D(k) = B(k) the k-th Bernoulli number.

A280537 Maximum number of points that can be selected from an n X n X n grid so that no four of them are in a plane.

Original entry on oeis.org

5, 8, 10, 13, 16, 18, 20

Offset: 2

Hugo Pfoertner, Jan 05 2017

Terms up to a(6) were found by exhaustive search. a(7) and a(8) are based on extensive numerical evidence.

Currently (January 2017) known lower bounds for the next terms are a(9)>=23, a(10)>=26, a(11)>=28, a(12)>=30, a(13)>=32, a(14)>=35, a(15)>=36, a(16)>=38, a(17)>=42.

Walter Möhres, Exhaustive Search for the 6x6x6 "No Four in Plane Problem". Private communication, September 2016.

Ed Pegg Jr, No-Four-In-Plane Problem, Wolfram Demonstrations Project.
Ed Pegg, No-Four-In-Plane, can 11 points be picked from a 4 X 4 X 4 grid?. Question in Mathematics Stack Exchange, a(4) and a(5) provided in answers.
Torsten Sillke, no 4 on a plane (3*3*3 puzzle), discussion in newsgroup rec.puzzles, Nov 27, 1992.
Al Zimmermann's Programming Contests, Non-Coplanar Points, March - June 2016.

Cf. A000769, A272651, A280538.

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

A103517 Expansion of (1+2*x-x^2)/(1-x)^2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

A279445 Triangle read by rows: T(n, k) is the number of ways to place k points on an n X n square grid so that no more than 2 points are on a vertical or horizontal straight line.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A279453 Triangle read by rows: T(n, k) is the number of nonequivalent ways to place k points on an n X n square grid so that no more than 2 points are on a vertical or horizontal straight line.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A326478 a(n) = n*denominator(n*Bernoulli(n-1))/denominator(Bernoulli(n-1)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A280537 Maximum number of points that can be selected from an n X n X n grid so that no four of them are in a plane.

Views

Author

Keywords

Comments

References

Links

Crossrefs

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

A326478 a(n) = ndenominator(nBernoulli(n-1))/denominator(Bernoulli(n-1)).