A279409 Triangle read by rows: T(n,m) (n>=m>=1) = maximum number of nonattacking kings on an n X m toroidal board.

1, 1, 1, 1, 1, 1, 2, 2, 2, 4, 2, 2, 2, 4, 5, 3, 3, 3, 6, 6, 9, 3, 3, 3, 6, 7, 9, 10, 4, 4, 4, 8, 8, 12, 12, 16, 4, 4, 4, 8, 9, 12, 13, 16, 18, 5, 5, 5, 10, 10, 15, 15, 20, 20, 25, 5, 5, 5, 10, 11, 15, 16, 20, 22, 25, 27, 6, 6, 6, 12, 12, 18, 18, 24, 24, 30, 30, 36

Offset

1,7

Comments

Independence number of the kings' graph on toroidal n X m chessboard.

Right border T(n,n) is A189889.

For the usual non-toroidal case, the formula is ceiling(m/2)*ceiling(n/2).

References

John J. Watkins, Across the Board: The Mathematics of Chessboard Problem, Princeton University Press, 2004, pages 194-196.

Links

Indranil Ghosh, Rows 1..125, flattened

Dan Freeman, Chessboard Puzzles Part 4 - Other Surfaces and Variations.

V. Kotesovec, Non-attacking chess pieces.

Formula

T(n,m) = floor(min(m*floor(n/2), n*floor(m/2))/2) for m>1;

T(n,1) = floor(n/2) for n>1.

Example

Triangle starts:
1;
1, 1;
1, 1, 1;
2, 2, 2, 4;
2, 2, 2, 4, 5;
3, 3, 3, 6, 6, 9;
3, 3, 3, 6, 7, 9, 10;
...

Mathematica

T[1, 1] = 1; T[n_, m_]:= If[m==1, Floor[n/2], Floor[Min[m Floor[n/2], n Floor[m/2]]/2]]; Flatten[Table[T[n, m], {n, 1, 12}, {m, 1, n}]] (* Indranil Ghosh, Mar 09 2017 *)

Prog

(PARI) tabl(nn) = {for(n=1, 12, for(m=1, n, print1(if(m==1, if(n==1, 1, floor(n/2)), floor(min(m*floor(n/2), n*floor(m/2))/2)), ", "); ); print(); ); };
tabl(12); \\ Indranil Ghosh, Mar 09 2017
(Python)
def T(n, m):
....if m==1:
........if n==1: return 1
........return n/2
....return min(m*(n/2), n*(m/2))/2
i=1
for n in range(1, 126):
....for m in range(1, n+1):
........print str(i)+" "+str(T(n, m))
........i+=1 # Indranil Ghosh, Mar 09 2017

Crossrefs

Cf. A085801, A189889, A279408.

Sequence in context: A102298 A049298 A075016 * A102445 A102430 A160691

Adjacent sequences: A279406 A279407 A279408 * A279410 A279411 A279412

Keyword

nonn,tabl,easy

Author

Andrey Zabolotskiy, Dec 16 2016

Status

approved