A240114 -id:A240114 - cp's OEIS frontend

A240439 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 of any orientation. Triangle read by rows.

1, 1, 1, 3, 3, 1, 6, 15, 15, 3, 1, 10, 45, 105, 114, 39, 3, 1, 15, 105, 420, 969, 1194, 654, 102, 3, 1, 21, 210, 1260, 4773, 11259, 15615, 11412, 3663, 342, 15, 1, 28, 378, 3150, 17415, 64776, 159528, 250233, 234609, 119259, 28395, 2613, 69, 1, 36, 630, 6930

Offset: 1

Heinrich Ludwig, Apr 05 2014

The triangle T(n, k) is irregularly shaped: 0 <= k <= A240114(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 is given by A240114(n).

			The triangle begins:
  1,  1;
  1,  3,   3;
  1,  6,  15,   15,    3;
  1, 10,  45,  105,  114,    39,     3;
  1, 15, 105,  420,  969,  1194,   654,   102,    3;
  1, 21, 210, 1260, 4773, 11259, 15615, 11412, 3663, 342, 15;
There are T(5, 8) = 3 ways to place 8 points (x) on a triangular grid of side 5 under the conditions mentioned above:
          .                x                x
         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..138

Cf. A240114, A240443, A084546,
column 2 is A000217,
column 3 is A050534,
column 4 is A240440,
column 5 is A240441,
column 6 is A240442.

A240443 Maximal number of points that can be placed on an n X n square grid so that no four of them are vertices of a square with any orientation.

Original entry on oeis.org

1, 3, 6, 10, 15, 21, 27, 34, 42, 50

Offset: 1

Heinrich Ludwig, May 07 2014

a(10) >= 50, a(11) >= 58. - Robert Israel, Apr 08 2016
a(12) >= 67. - Robert Israel, Apr 12 2016
a(13) >= 76, a(14) >= 86, a(15) >= 95, a(16) >= 106. - Peter Karpov, Jun 04 2016

			On a 9 X 9 grid a maximum of 42 points (x) can be placed so that no four of them are vertices of an (arbitrarily oriented) square. An example:
     x x . . x . x . x
     . x . . x x x x .
     x x x . . x . . x
     x . x x x . . x x
     . . . . x x . . .
     . x . x x . . . x
     x x x . x . . . x
     x . x . . . . x x
     x . . x x x x x .

Robert Israel, Illustration showing a(10) >= 50
Robert Israel, Illustration showing a(11) >= 58
Robert Israel, Illustration showing a(12) >= 67
Peter Karpov, Maximal density subsquare-free arrangements / #Optimization #OpenProblem / 2016.02.22, giving lower bounds for a(1)-a(16).
Peter Karpov, Best configurations known for n = 13 .. 16
Giovanni Resta, Illustration of a(8) and a(9)
Dominik Stadlthanner, Python program
Ed Wynn, A comparison of encodings for cardinality constraints in a SAT solver, arXiv:1810.12975 [cs.LO], 2018.

Cf. A227133 (where we are concerned only with subsquares oriented parallel to the sides of the grid), A240114, A227308, A240444.

a(10) from Dominik Stadlthanner using integer programming, Apr 08 2020

A243141 Triangle T(n, k) = Numbers of inequivalent (mod D_3) ways to place k points on a triangular grid of side n so that no three of them are vertices of an equilateral triangle of any orientation. Triangle read by rows.

Original entry on oeis.org

1, 1, 1, 2, 4, 3, 1, 3, 10, 19, 22, 7, 1, 4, 22, 75, 170, 204, 115, 18, 1, 5, 41, 218, 816, 1891, 2635, 1909, 628, 58, 3, 7, 72, 542, 2947, 10846, 26695, 41770, 39218, 19905, 4776, 437, 13, 8, 116, 1178, 8765, 46068, 171700, 444117, 776276, 876012, 601078, 229941

Offset: 1

Heinrich Ludwig, May 30 2014

The triangle T(n, k) is irregularly shaped: 1 <= k <= A240114(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 is given by A240114(n).

			The triangle begins:
  1;
  1,  1;
  2,  4,   3,    1;
  3, 10,  19,   22,     7,     1;
  4, 22,  75,  170,   204,   115,    18,     1;
  5, 41, 218,  816,  1891,  2635,  1909,   628,    58,    3;
  7, 72, 542, 2947, 10846, 26695, 41770, 39218, 19905, 4776, 437, 13;
  ...
There is exactly T(5, 8) = 1 way to place 8 points (x) on a triangular grid of side 5 according to the definition of the sequence:
           .
          x x
         x . x
        x . . x
       x . . . x

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

Cf. A240114, A240439, A001399 (column 1), A227327 (column 2), A243142 (column 3), A243143 (column 4), A243144 (column 5).

A319159 Given an equilateral triangular grid with side n, containing n(n+1)/2 points, a(n) is the minimal number of points to be selected, such that any equilateral triangle of points will include at least one of the selection.

Original entry on oeis.org

1, 2, 4, 7, 11, 16, 22, 28, 35, 44, 53, 63, 74, 86

Offset: 1

Ed Wynn, Sep 12 2018

This is the complementary problem to A240114: a(n) + A240114(n) = n(n+1)/2.

This is the same problem as A227116 and A319158, except that here the triangles may have any orientation. Due to the additional requirements, a(n) >= A227116(n) >= A319158(n).

			For n=4, this sequence has the same value a(4)=4 as A227116 and A319158, but if we look at the three solutions to those sequences (unique up to symmetry), representing selected points by O:
        O             O             O
       O ,           . ,           . .
      , . O         , O .         . O .
     . O , .       O . , O       . O O .
We see that only the last of these is a solution here -- the others have rotated triangles not including any selected point (for example, as shown with commas).  The last selection is therefore the unique solution (up to symmetry) for a(4)=4.

Ed Wynn, A comparison of encodings for cardinality constraints in a SAT solver, arXiv:1810.12975 [cs.LO], 2018.

Cf. A227116, A240114, A319158.

A350547 Maximum size of a set of points taken from a hexagonal section of a hexagonal grid with side length n such that no three selected points form an equilateral triangle.

Original entry on oeis.org

1, 4, 9, 15, 22, 28, 36

Offset: 0

Zachary DeStefano, Jan 06 2022

The hexagon with side length n has n+1 points along each edge and contains a total of A003215(n) points.
The following lower bounds are known:
a(7) >= 44;
a(8) >= 52;
a(9) >= 60.
All currently known values and lower bounds can be achieved by a configuration with reflective symmetry.

			For n = 4 the a(4) = 22 solution, unique up to rotation, is:
.
      o x x o x
     x x o o o x
    x o o o o x o
   o o o o o o x x
  x o o o o o o o x
   x x o o o o o o
    o x o o o o x
     x o o o x x
      x o x x o
.

Cf. A003215, A008893, A240114.

cp's OEIS Frontend

A240439 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 of any orientation. Triangle read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A240443 Maximal number of points that can be placed on an n X n square grid so that no four of them are vertices of a square with any orientation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A243141 Triangle T(n, k) = Numbers of inequivalent (mod D_3) ways to place k points on a triangular grid of side n so that no three of them are vertices of an equilateral triangle of any orientation. Triangle read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A319159 Given an equilateral triangular grid with side n, containing n(n+1)/2 points, a(n) is the minimal number of points to be selected, such that any equilateral triangle of points will include at least one of the selection.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A350547 Maximum size of a set of points taken from a hexagonal section of a hexagonal grid with side length n such that no three selected points form an equilateral triangle.

Views

Author

Keywords

Comments

Examples

Crossrefs