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