A194136 -id:A194136 - cp's OEIS frontend

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.

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

Offset: 1

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

A234350 Triangle T(n, k) = Number of non-equivalent (mod D_3) ways to arrange k indistinguishable points on a triangular grid of side n so that no three points are collinear. Triangle read by rows.

Original entry on oeis.org

1, 1, 1, 1, 2, 4, 5, 2, 3, 10, 22, 24, 8, 1, 4, 22, 77, 153, 140, 47, 2, 5, 41, 217, 713, 1290, 1112, 322, 15, 7, 72, 530, 2557, 7374, 11743, 8783, 2412, 143, 1, 8, 116, 1149, 7661, 32477, 82988, 116154, 77690, 19621, 1220, 5, 10, 180, 2288, 20055, 116420, 433372

Offset: 1

Heinrich Ludwig, Dec 24 2013

The triangle T(n, k) is irregularly shaped: 1 <= k <= A234349(n). First row corresponds to n = 1.
The maximal number of points that can be placed on a triangular grid of side n so that no three points are collinear is given by A234349(n).
Without the restriction "non-equivalent (mod D_3)" the numbers are given by A194136.

			Triangle begins
1;
1,   1,    1;
2,   4,    5,    2;
3,  10,   22,   24,     8,     1;
4,  22,   77,  153,   140,    47,      2;
5,  41,  217,  713,  1290,  1112,    322,    15;
7,  72,  530, 2557,  7374, 11743,   8783,  2412,   143,    1;
8, 116, 1149, 7661, 32477, 82988, 116154, 77690, 19621, 1220, 5;
...
There are e.g. T(8, 11) = 5 non-equivalent ways to arrange 11 indistinguishable points (X) on a triangular grid of side 8 so that no point triple is collinear. As examples of the 5 solutions the 2 symmetrical ones are shown.
          .                    .
         . .                  . .
        . X .                . X .
       X . . X              X . . X
      X . . . X            . X . X .
     . . X X . .          X . . . . X
    . X . . . X .        . . X . X . .
   . . X . . X . .      . . X . . X . .

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

Cf. A194136
Row lengths are given by A234349
Column 1 is A001399
Column 2 is A227327 for n >= 2
Column 3 is A234351
Column 4 is A234352
Column 5 is A234353
Column 6 is A234354.

A243211 Triangle T(n, k) = Numbers of ways to place k points on a triangular grid of side n so that no three of them are vertices of an equilateral triangle with sides parallel to the grid. Triangle read by rows.

Original entry on oeis.org

1, 1, 1, 3, 3, 1, 6, 15, 15, 3, 1, 10, 45, 107, 128, 63, 10, 1, 15, 105, 428, 1062, 1566, 1276, 507, 69, 1, 21, 210, 1282, 5160, 13971, 25191, 29235, 20508, 7747, 1251, 42, 1, 1, 28, 378, 3198, 18591, 77124, 231090, 498097, 759117, 792942, 540361, 222597, 49053

Offset: 1

Heinrich Ludwig, Jun 09 2014

The triangle T(n, k) is irregularly shaped: 0 <= k <= A227308(n). First row corresponds to n = 1.

The maximal number of points that can be placed on a triangular grid of side n so that no three of them form an equilateral triangle with sides parallel to the grid is given by A227308(n).

			The triangle begins:
  1,  1;
  1,  3,   3;
  1,  6,  15,   15,    3;
  1, 10,  45,  107,  128,    63,    10,
  1, 15, 105,  428, 1062,  1566,  1276,   507,    69,
  1, 21, 210, 1282, 5160, 13971, 25191, 29235, 20508, 7747, 1251, 42, 1;
  ...
There is T(6, 12) = 1 way to place 12 points (x) on the grid obeying the rule in the definition of the sequence:
           .
          x x
         x . x
        x . . x
       x . . . x
      . x x x x .

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

Cf. A227308, A243207, A084546, A234251, A239567, A240439, A194136, A000217 (column 2), A050534 (column 3), A243212 (column 4), A243213 (column 5), A243214 (column 6).

A194131 Number of ways to arrange 3 indistinguishable points on an n X n X n triangular grid so that no three points are collinear at any angle.

Original entry on oeis.org

0, 0, 1, 17, 105, 407, 1216, 3036, 6696, 13428, 25005, 43861, 73277, 117471, 181880, 273268, 399960, 572076, 801825, 1103625, 1494541, 1994387, 2626152, 3416300, 4395148, 5596992, 7060737, 8830137, 10954197, 13487527, 16490972, 20031672

Offset: 0

R. H. Hardin, Aug 17 2011

nonn

Column 3 of A194136.

			Some solutions for 3X3X3
....0......1......1......0......1......1......1......0......0......1......0
...1.1....1.0....0.1....1.0....0.0....0.0....1.1....1.1....0.1....0.1....0.1
..0.0.1..0.0.1..1.0.0..1.1.0..0.1.1..1.0.1..0.0.0..0.1.0..1.1.0..0.1.0..1.0.1

N. J. A. Sloane, Table of n, a(n) for n = 0..500, Mar 20 2016 [First 196 terms from _R. H. Hardin_]
StackExchange, Number of possible triangles in a given triangle.

Cf. A194136.

a(n) = ((n^2+n+2)/2) * binomial(n+2,4) - (3/2) * Sum_{k=2..n} (n-k+1) * (n-k+2) * Sum_{m=2..k} gcd(k-1,m-1). - David Bevan, Jan 01 2012

A194132 Number of ways to arrange 4 indistinguishable points on an n X n X n triangular grid so that no three points are collinear at any angle.

Original entry on oeis.org

0, 0, 6, 114, 843, 4122, 14988, 45414, 119340, 281442, 608616, 1228812, 2338779, 4240284, 7371414, 12354156, 20052846, 31653108, 48726846, 73358964, 108233781, 156793974, 223400004, 313529940, 433929258, 592922880, 800651538, 1069378740

Offset: 1

R. H. Hardin, Aug 17 2011

nonn

Column 4 of A194136.

			All solutions for 3 X 3 X 3:
....1......1......0......0......1......0
...0.1....1.1....1.1....1.1....1.0....1.1
..1.1.0..0.1.0..1.1.0..1.0.1..0.1.1..0.1.1

R. H. Hardin, Table of n, a(n) for n = 1..78

A194133 Number of ways to arrange 5 indistinguishable points on an n X n X n triangular grid so that no three points are collinear at any angle.

Original entry on oeis.org

0, 0, 0, 39, 792, 7587, 43836, 194013, 696765, 2145687, 5851044, 14546412, 33347130, 71662911, 145616964, 281816991, 522786390, 935155011, 1618729257, 2722297371, 4459330956, 7133246976, 11168002962, 17149002624, 25863493314, 38369771853

Offset: 1

R. H. Hardin, Aug 17 2011

nonn

Column 5 of A194136.

			Some solutions for 4 X 4 X 4:
.....1........0........0........1........0........0........0........1
....0.1......1.0......0.1......0.0......1.1......0.1......0.1......1.0
...0.1.0....0.1.1....1.0.1....1.1.0....1.0.1....1.1.0....0.1.1....0.1.0
..1.0.1.0..0.1.0.1..1.0.1.0..0.1.0.1..0.1.0.0..1.0.0.1..1.0.1.0..0.1.0.1

R. H. Hardin, Table of n, a(n) for n = 1..42

A194134 Number of ways to arrange 6 indistinguishable points on an n X n X n triangular grid so that no three points are collinear at any angle.

Original entry on oeis.org

0, 0, 0, 1, 244, 6480, 69798, 496198, 2595897, 10912452, 38739354, 121694240, 342722071, 887407361, 2136513884, 4828507719, 10332712952, 21117591802, 41392701372, 78248425161, 143087468105, 253946607496, 438734862156

Offset: 1

R. H. Hardin, Aug 17 2011

nonn

Column 6 of A194136.

			Some solutions for 5 X 5 X 5:
......1..........1..........1..........0..........0..........0..........0
.....0.1........1.0........0.0........0.1........1.0........1.1........1.1
....1.0.0......0.0.0......1.0.0......1.0.1......0.1.1......0.0.1......0.0.0
...0.0.1.0....0.1.1.0....0.1.0.1....1.0.1.0....0.1.0.0....1.0.0.0....1.0.0.1
..0.1.1.0.0..0.0.1.0.1..0.1.0.1.0..0.0.0.1.0..0.0.1.0.1..0.1.0.1.0..0.1.0.1.0

R. H. Hardin, Table of n, a(n) for n = 1..27

A234349 Maximal number of points that can be placed on a triangular grid of side n so that no three points are collinear.

Original entry on oeis.org

1, 3, 4, 6, 7, 8, 10, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 25, 27, 28

Offset: 1

Heinrich Ludwig, Dec 24 2013

Length of the n-th row in triangle A194136 and triangle A234350.

Differs from A007401 first at n=14.

			In a triangular grid of side 5 at most 7 points (x) can be placed so that no three of them are on a straight line. (There are exactly 2 ways to do it, rotations and reflections ignored.)
        .              x
       . x            . .
      x . x          x . x
     x . x .        . x x .
    . x . x .      . x . x .

Cf. A194136, A234350.

a(13)-a(14) from Heinrich Ludwig, Jan 10 2014
a(15)-a(16) from Heinrich Ludwig, Jan 28 2014
a(17)-a(21) from Rob Pratt, Jul 27 2015

A358532 a(n) is the row position of the next open point in the structure generated by adding the largest diamond possible at the next open point on a triangular grid of side n. See Comments and Example sections for more details.

Original entry on oeis.org

1, 1, 2, 1, 2, 3, 1, 4, 1, 3, 7, 1, 3, 6, 4, 10, 1, 9, 4, 7, 9, 5, 14, 1, 11, 5, 7, 8, 11, 14, 19, 1, 6, 6, 24, 9, 14, 20, 1, 8, 8, 8, 20, 8, 19, 24, 30, 15, 19, 19, 19, 27, 1, 19, 15, 16, 20, 28, 8, 39, 11, 24, 1, 11, 16, 26, 28, 29, 30, 39, 50, 20, 31, 32, 33

Offset: 1

John Tyler Rascoe, Nov 20 2022

A structure of diamonds is built up successively by adding the largest possible diamond to the next open point within a triangular grid of side n. Each new diamond is added to the preceding structure of diamonds. At each step n, a new row of n open points is first added, extending the triangular grid.
Then the next open point is defined as the first open point encountered when the triangle is read by rows starting from the top row. a(n) is then the row position of the next open point.
Finally, starting at this open point the largest diamond that does not overlap any previous diamonds and fits within the triangular grid is added. Each diamond of side length k must cover exactly k^2 points, with the top corner on an open point. The points covered by the added diamond are then considered closed.
Is there a pattern for the values of n where a(n) = 1?

			Here zeros are the open points; closed points covered by the n-th diamond are replaced with n.
  ---------------------
  n=4       1          First a new row of 4 open points is added.
           2 3         Then the next open point is T(3,1) so a(4) = 1.
          4 0 0        Finally, the largest diamond fitting at T(3,1) is 1.
         0 0 0 0
  ---------------------
  n=5       1          First a new row of 5 open points is added.
           2 3         Then the next open point is T(3,2) so a(5) = 2.
          4 5 0        Finally, the largest diamond fitting at T(3,2) is 2.
         0 5 5 0
        0 0 5 0 0
  ---------------------
  n=6       1          First a new row of 6 open points is added.
           2 3         Then the next open point is T(3,3) so a(6) = 3.
          4 5 6        Finally, the largest diamond fitting at T(3,3) is 1.
         0 5 5 0
        0 0 5 0 0
       0 0 0 0 0 0

John Tyler Rascoe, Table of n, a(n) for n = 1..10000
John Tyler Rascoe, Python program

Cf. A045996, A186434, A194136, A239567, A279413.

Python
```
# see linked program
```

A194135 Number of ways to arrange 7 indistinguishable points on an n X n X n triangular grid so that no three points are collinear at any angle.

Original entry on oeis.org

0, 0, 0, 0, 9, 1875, 52323, 695616, 5840088, 35715529, 172520643, 708871152, 2517687856, 8023634766, 23292994812, 62357664744, 155765126265, 367482996726, 822866800569, 1762214894004, 3621792301059

Offset: 1

R. H. Hardin, Aug 17 2011

nonn

Column 7 of A194136.

			Some solutions for 5 X 5 X 5:
......0..........0..........0..........0..........0..........0..........0
.....0.1........1.0........1.0........0.1........0.1........1.0........1.1
....1.0.1......1.0.1......0.1.1......1.1.0......1.1.0......0.1.1......0.0.1
...1.0.1.0....0.1.0.1....1.0.0.1....1.0.0.1....0.0.1.1....1.1.0.0....1.1.0.0
..0.1.0.1.0..0.1.0.1.0..0.1.1.0.0..0.0.1.1.0..1.0.1.0.0..0.0.1.0.1..0.0.1.1.0

cp's OEIS Frontend

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

A234350 Triangle T(n, k) = Number of non-equivalent (mod D_3) ways to arrange k indistinguishable points on a triangular grid of side n so that no three points are collinear. Triangle read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A243211 Triangle T(n, k) = Numbers of ways to place k points on a triangular grid of side n so that no three of them are vertices of an equilateral triangle with sides parallel to the grid. Triangle read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A194131 Number of ways to arrange 3 indistinguishable points on an n X n X n triangular grid so that no three points are collinear at any angle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A194132 Number of ways to arrange 4 indistinguishable points on an n X n X n triangular grid so that no three points are collinear at any angle.

Views

Author

Keywords

Comments

Examples

Links

A194133 Number of ways to arrange 5 indistinguishable points on an n X n X n triangular grid so that no three points are collinear at any angle.

Views

Author

Keywords

Comments

Examples

Links

A194134 Number of ways to arrange 6 indistinguishable points on an n X n X n triangular grid so that no three points are collinear at any angle.

Views

Author

Keywords

Comments

Examples

Links

A234349 Maximal number of points that can be placed on a triangular grid of side n so that no three points are collinear.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A358532 a(n) is the row position of the next open point in the structure generated by adding the largest diamond possible at the next open point on a triangular grid of side n. See Comments and Example sections for more details.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

A194135 Number of ways to arrange 7 indistinguishable points on an n X n X n triangular grid so that no three points are collinear at any angle.

Views

Author

Keywords

Comments