OFFSET
0,3
COMMENTS
In other words, independence number of the n X n knight graph. - Eric W. Weisstein, May 05 2017
Also the upper irredundance number of the n X n knight graph. - Eric W. Weisstein, Dec 27 2025
REFERENCES
H. E. Dudeney, The Knight-Guards, #319 in Amusements in Mathematics; New York: Dover, p. 95, 1970.
J. S. Madachy, Madachy's Mathematical Recreations, New York, Dover, pp. 38-39 1979.
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 751.
Eric Weisstein's World of Mathematics, Independence Number.
Eric Weisstein's World of Mathematics, Knight Graph.
Eric Weisstein's World of Mathematics, Knights Problem.
Eric Weisstein's World of Mathematics, Upper Irredundance Number.
Index entries for linear recurrences with constant coefficients, signature (2,0,-2,1).
FORMULA
a(n) = 4 if n = 2, n^2/2 if n even > 2, (n^2+1)/2 if n odd > 1.
a(n) = 4 if n = 2, (1 + (-1)^(1 + n) + 2 n^2)/4 otherwise.
G.f.: x*(2*x^5-4*x^4+3*x^2-2*x-1) / ((x-1)^3*(x+1)). - Colin Barker, Jan 09 2013
E.g.f.: (2*x^2 + x*(1 + x)*cosh(x) + (1 + x + x^2)*sinh(x))/2. - Stefano Spezia, Dec 27 2025
Sum_{n>=1} 1/a(n) = (Pi/2)*tanh(Pi/2) + Pi^2/12 - 1/4. - Amiram Eldar, Dec 28 2025
MATHEMATICA
CoefficientList[Series[x (2 x^5 - 4 x^4 + 3 x^2 - 2 x - 1)/((x - 1)^3 (x + 1)), {x, 0, 60}], x] (* Vincenzo Librandi, Oct 19 2013 *)
Join[{0, 1, 4}, Table[If[EvenQ[n], n^2/2, (n^2 + 1)/2], {n, 3, 60}]] (* Harvey P. Dale, Nov 28 2014 *)
Join[{0, 1, 4}, LinearRecurrence[{2, 0, -2, 1}, {5, 8, 13, 18}, 60]] (* Harvey P. Dale, Nov 28 2014 *)
Table[If[n == 2, 4, (1 - (-1)^n + 2 n^2)/4], {n, 20}] (* Eric W. Weisstein, May 05 2017 *)
Table[Length[FindIndependentVertexSet[KnightTourGraph[n, n]][[1]]], {n, 20}] (* Eric W. Weisstein, Jun 27 2017 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
EXTENSIONS
More terms from Erich Friedman
Definition clarified by Vaclav Kotesovec, Sep 16 2014
STATUS
approved
