cp's OEIS Frontend

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

%I A189889 #63 Feb 16 2025 08:33:14
%S A189889 1,1,1,4,5,9,10,16,18,25,27,36,39,49,52,64,68,81,85,100,105,121,126,
%T A189889 144,150,169,175,196,203,225,232,256,264,289,297,324,333,361,370,400,
%U A189889 410,441,451,484,495,529,540,576,588,625
%N A189889 Maximum number of nonattacking kings on an n X n toroidal board.
%C A189889 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 A189889 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 A189889 John Watkins, Across the Board: The Mathematics of Chessboard Problems (2004), Theorem 11.1, p.194.
%H A189889 Vincenzo Librandi, <a href="/A189889/b189889.txt">Table of n, a(n) for n = 1..1000</a>
%H A189889 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 A189889 Vaclav Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Non-attacking chess pieces</a>, 6ed, 2013, p. 751.
%H A189889 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/KingsProblem.html">Kings Problem</a>.
%H A189889 <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,-1,1,-1,-1,1).
%F A189889 a(n) = floor((n*floor(n/2))/2), n > 1 (Watkins and Ricci, 2004).
%F A189889 a(n) = a(n-1) + a(n-2) - a(n-3) + a(n-4) - a(n-5) - a(n-6) + a(n-7).
%F A189889 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 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 A189889 Table[If[n==1,1,Floor[(n*Floor[n/2])/2]],{n,1,50}]
%t A189889 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 A189889 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 A189889 (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 A189889 (PARI) a(n) = if(n==1, 1, floor((n*floor(n/2))/2)); \\ _Indranil Ghosh_, Mar 09 2017
%o A189889 (Python) def A189889(n): return 1 if n==1 else (n*(n/2))/2 # _Indranil Ghosh_, Mar 09 2017
%o A189889 (Magma) [1] cat [Floor(n*Floor(n/2)/2): n in [2..50]]; // _G. C. Greubel_, Jan 13 2018
%Y A189889 Cf. A018807, A085801, A172158, A174558, A179428, A180067.
%K A189889 nonn,easy
%O A189889 1,4
%A A189889 _Vaclav Kotesovec_, Apr 30 2011