A189889 Maximum number of nonattacking kings on an n X n toroidal board.

1, 1, 1, 4, 5, 9, 10, 16, 18, 25, 27, 36, 39, 49, 52, 64, 68, 81, 85, 100, 105, 121, 126, 144, 150, 169, 175, 196, 203, 225, 232, 256, 264, 289, 297, 324, 333, 361, 370, 400, 410, 441, 451, 484, 495, 529, 540, 576, 588, 625

Offset: 1

Author

Vaclav Kotesovec, Apr 30 2011

Keywords

• nonn
• easy

Comments

a(n) is the independence number of the Cayley graph on the group Z_n X Z_n with generators (+-e_1, +-e_2)<>(0,0) where e_i is in {0,1} for i=1,2. - Miquel A. Fiol, Aug 07 2024

For n>=4 a(n) is the maximum number of edges of an n-cycle graph with chords not containing any triangle with some edges of the cycle. - Miquel A. Fiol, Sep 20 2024

References

• John Watkins, Across the Board: The Mathematics of Chessboard Problems (2004), Theorem 11.1, p.194.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..1000
• Hernan de Alba, W. Carballosa, J. Leaños, and L. M. Rivera, Independence and matching numbers of some token graphs, arXiv preprint arXiv:1606.06370 [math.CO], 2016.
• Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 751.
• Eric Weisstein's World of Mathematics, Kings Problem.
• Index entries for linear recurrences with constant coefficients, signature (1,1,-1,1,-1,-1,1).

Crossrefs

Cf. A018807, A085801, A172158, A174558, A179428, A180067.

Programs

Magma

[1] cat [Floor(n*Floor(n/2)/2): n in [2..50]]; // G. C. Greubel, Jan 13 2018

Maple

A189889:=n->`if`(n=1,1,floor(n*floor(n/2)/2)); seq(A189889(k), k=1..100); # Wesley Ivan Hurt, Nov 07 2013

Mathematica

Table[If[n==1,1,Floor[(n*Floor[n/2])/2]],{n,1,50}]
CoefficientList[Series[(- x^7 + x^6 + x^5 + 3 * x^3 - x^2 + 1) / (-x^7 + x^6 + x^5 - x^4 + x^3 - x^2 - x + 1), {x, 0, 50}], x] (* Vincenzo Librandi, Jun 02 2013 *)
Join[{1},LinearRecurrence[{1,1,-1,1,-1,-1,1},{1,1,4,5,9,10,16},50]] (* Harvey P. Dale, Aug 07 2013 *)

PARI

Vec(x*(-x^7 + x^6 + x^5 + 3*x^3 - x^2 + 1) / (-x^7 + x^6 + x^5 - x^4 + x^3 - x^2 - x + 1) + O(x^51)) \\ Indranil Ghosh, Mar 09 2017

PARI

a(n) = if(n==1, 1, floor((n*floor(n/2))/2)); \\ Indranil Ghosh, Mar 09 2017

Python

def A189889(n): return 1 if n==1 else (n*(n/2))/2 # Indranil Ghosh, Mar 09 2017

Formula

a(n) = floor((n*floor(n/2))/2), n > 1 (Watkins and Ricci, 2004).

a(n) = a(n-1) + a(n-2) - a(n-3) + a(n-4) - a(n-5) - a(n-6) + a(n-7).

G.f.: x*(-x^7 +x^6 +x^5 +3*x^3 -x^2 +1) / (-x^7 +x^6 +x^5 -x^4+ x^3 -x^2 -x +1).