%I #62 Sep 20 2024 06:39:04

%S 1,1,1,4,5,9,10,16,18,25,27,36,39,49,52,64,68,81,85,100,105,121,126,

%T 144,150,169,175,196,203,225,232,256,264,289,297,324,333,361,370,400,

%U 410,441,451,484,495,529,540,576,588,625

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

%C 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

%C 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

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

%H Vincenzo Librandi, <a href="/A189889/b189889.txt">Table of n, a(n) for n = 1..1000</a>

%H Hernan de Alba, W. Carballosa, J. Leaños, and L. M. Rivera, <a href="https://arxiv.org/abs/1606.06370">Independence and matching numbers of some token graphs</a>, arXiv preprint arXiv:1606.06370 [math.CO], 2016.

%H Vaclav Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Non-attacking chess pieces</a>, 6ed, 2013, p. 751.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/KingsProblem.html">Kings Problem</a>.

%H <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,-1,1,-1,-1,1).

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

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

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

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

%t Table[If[n==1,1,Floor[(n*Floor[n/2])/2]],{n,1,50}]

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

%t Join[{1},LinearRecurrence[{1,1,-1,1,-1,-1,1},{1,1,4,5,9,10,16},50]] (* _Harvey P. Dale_, Aug 07 2013 *)

%o (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

%o (PARI) a(n) = if(n==1, 1, floor((n*floor(n/2))/2)); \\ _Indranil Ghosh_, Mar 09 2017

%o (Python) def A189889(n): return 1 if n==1 else (n*(n/2))/2 # _Indranil Ghosh_, Mar 09 2017

%o (Magma) [1] cat [Floor(n*Floor(n/2)/2): n in [2..50]]; // _G. C. Greubel_, Jan 13 2018

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

%K nonn,easy

%O 1,4

%A _Vaclav Kotesovec_, Apr 30 2011