login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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

%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