login
A189889
Maximum number of nonattacking kings on an n X n toroidal board.
9
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,4
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
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.
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).
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 *)
PROG
(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
(Magma) [1] cat [Floor(n*Floor(n/2)/2): n in [2..50]]; // G. C. Greubel, Jan 13 2018
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Vaclav Kotesovec, Apr 30 2011
STATUS
approved