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

Author

Andrey Zabolotskiy, Dec 16 2016

Keywords

• nonn
• tabl
• easy

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).

Examples

			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;
  ...
		

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.
• Vaclav Kotesovec, Non-attacking chess pieces.

Crossrefs

Cf. A085801, A189889, A279408.

Programs

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 *)

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(i, T(n,m))
        i+=1 # Indranil Ghosh, Mar 09 2017

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.