A181018 -id:A181018 - cp's OEIS frontend

A181019 T(n,k) = maximum number of 1s in an n X k binary matrix with no three 1s adjacent in a line along a row, column or diagonally.

1, 2, 2, 2, 4, 2, 3, 4, 4, 3, 4, 6, 6, 6, 4, 4, 8, 7, 7, 8, 4, 5, 8, 9, 9, 9, 8, 5, 6, 10, 10, 12, 12, 10, 10, 6, 6, 12, 12, 13, 16, 13, 12, 12, 6, 7, 12, 14, 16, 17, 17, 16, 14, 12, 7, 8, 14, 15, 18, 20, 20, 20, 18, 15, 14, 8, 8, 16, 17, 20, 24, 23, 23, 24, 20, 17, 16, 8, 9, 16, 19, 22, 25, 26

Offset: 1

R. H. Hardin, Sep 30 2010

For the diagonal (square arrays, k = n), see A181018. - M. F. Hasler, Jan 19 2016

			The table starts:
  1..2..2..3..4..4..5..6..6..7..8..8..9.10.10.11.12.12.13..14..14
  2..4..4..6..8..8.10.12.12.14.16.16.18.20.20.22.24.24.26..28..28
  2..4..6..7..9.10.12.14.15.17.19.20.22.24.25.27.29.30.32..34..35
  3..6..7..9.12.13.16.18.20.22.24.26.28.30.32.34.37.39.41..43..45
  4..8..9.12.16.17.20.24.25.28.32.33.36.40.41.44.48.49.52..56..57
  4..8.10.13.17.20.23.26.29.32.36.38.41.45.48.51.54.57.60..63..66
  5.10.12.16.20.23.26.30.33.37.41.44.48.51.55.58.62.65.69..72..76
  6.12.14.18.24.26.30.36.38.42.48.50.54.60.62.66.72.74.78..84..86
  6.12.15.20.25.29.33.38.42.47.52.56.60.66.70.74.79.83.88..92..96
  7.14.17.22.28.32.37.42.47.52.58.62.67.72.77.82.87.92.98.102.107
The unique maximal solution for 5X5 is the following:
  1..1..0..1..1
  1..1..0..1..1
  0..0..0..0..0
  1..1..0..1..1
  1..1..0..1..1

R. H. Hardin and Peter J. Taylor, Table of n, a(n) for n = 1..496 (first 220 terms from R. H. Hardin)

Cf. A181018.

A260090 Maximum number of kings on an n X n chessboard such that no king attacks more than one other king.

Original entry on oeis.org

1, 2, 4, 8, 12, 16, 21, 26, 33, 40, 48, 56, 65, 74, 85, 96, 108, 120, 133, 146, 161, 176, 192, 208, 225, 242, 261, 280, 300, 320, 341, 362, 385, 408, 432, 456, 481, 506, 533, 560, 588, 616, 645, 674, 705, 736, 768, 800, 833, 866, 901, 936, 972, 1008, 1045

Offset: 1

Rob Pratt, Jul 15 2015

Suggested by a problem involving parking cars in Marx (2015). The Marx problem is slightly different, however, since a solution in her book shows one car that is adjacent to two of its eight neighbors.
Can be formulated as an integer linear programming problem as follows. Define a graph with a node for each cell and an edge for each pair of cells that are a king's move apart. Let binary variable x[i] = 1 if a king appears at node i, and 0 otherwise. The objective is to maximize sum x[i]. Let N[i] be the set of neighbors of node i. To enforce the rule that x[i] = 1 implies sum {j in N[i]} x[j] <= 1, impose the linear constraint sum {j in N[i]} x[j] - 1 <= (|N[i]| - 1) * (1 - x[i]) for each i. - Rob Pratt, Jul 16 2015
An alternative formulation uses constraints x[i] + x[j] + x[k] <= 2 for each forbidden triple of nodes.

			a(8) = 26:
  XX_XX_XX
  ________
  XX_XX_XX
  ________
  XX_XX_X_
  _______X
  X_X_X___
  X_X_X_XX
a(15) = 85:
  XX_XX_XX_XX_X_X
  ____________X_X
  XX_X_X_X_XX____
  ___X_X_X____X_X
  XX_______XX_X_X
  ___XX_XX_______
  XX_______X_X_XX
  ___X_X_X_X_X___
  XX_X_X_______XX
  _______XX_XX___
  X_X_XX_______XX
  X_X____X_X_X___
  ____XX_X_X_X_XX
  X_X____________
  X_X_XX_XX_XX_XX

Dale Gerdemann et al., Discussions on Sequence Fans Mailing List, July 15 2015.
Patricia Marx, Let's Be Less Stupid, Hachette, 2015.

Yifan Xie, Table of n, a(n) for n = 1..10000
Manfred Scheucher, Python Script

A103139(n) and A181018(n) are upper bounds.
A260113 is the corresponding sequence for queens.
Cf. A103469, A381749.

a(n)=if(n==3, 4, (n*(n+2) + if(n%3 == 2, 1, 0) - 3*if(n%6 == 2, 1, 0))/3); \\ Yifan Xie, Mar 22 2025

Conjecture: For n != 3, a(n) = n(n+2)/3 + [n mod 3 = 2]/3 - [n mod 6 = 2]
Equivalent conjecture for n >= 5: a(n) = a(n-1) + n - A103469(n-2). - Bob Selcoe, Jul 17 2015
See A381749 for proofs of the conjectures. - Yifan Xie, Mar 22 2025

More terms from Yifan Xie, Mar 22 2025

A261212 Maximum number of 1's in an fully symmetrical n X n binary matrix with no three 1's adjacent in a line along a row, column or diagonally.

Original entry on oeis.org

1, 4, 4, 8, 16, 20, 25, 36, 41, 48, 64, 72, 81, 100, 109, 120, 144, 156, 173, 196, 213, 228, 256, 272, 300, 324, 349, 368, 401, 424, 457, 484

Offset: 1

V.J. Pohjola and Giovanni Resta, Aug 12 2015

nonn

Fully symmetrical refers to the four symmetry axes: horizontal, vertical and two diagonal.

Note that a(3k+2) = 4*(1+k)^2, for k=0,...,8, but a(29) = 401.

			For n=4, the matrix is
0 1 0
1 0 1
0 1 0
For n=6, the matrix is
1 1 0 0 1 1
1 0 1 1 0 1
0 1 0 0 1 0
0 1 0 0 1 0
1 0 1 1 0 1
1 1 0 0 1 1

Giovanni Resta, Illustration of a(6)-a(30)

Cf. A181018.

a(n) <= A181018(n).

a(3k+2) >= 4*(k+1)^2.

cp's OEIS Frontend

A181019 T(n,k) = maximum number of 1s in an n X k binary matrix with no three 1s adjacent in a line along a row, column or diagonally.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A260090 Maximum number of kings on an n X n chessboard such that no king attacks more than one other king.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A261212 Maximum number of 1's in an fully symmetrical n X n binary matrix with no three 1's adjacent in a line along a row, column or diagonally.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula