VOOZH about

URL: https://oeis.org/A030978

⇱ A030978 - OEIS

login
A030978
Maximal number of non-attacking knights on an n X n board.
11
0, 1, 4, 5, 8, 13, 18, 25, 32, 41, 50, 61, 72, 85, 98, 113, 128, 145, 162, 181, 200, 221, 242, 265, 288, 313, 338, 365, 392, 421, 450, 481, 512, 545, 578, 613, 648, 685, 722, 761, 800, 841, 882, 925, 968, 1013, 1058, 1105, 1152, 1201, 1250, 1301, 1352, 1405
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
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.
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
Agrees with A000982 for n>2.
Cf. A244081.
Sequence in context: A133940 A174398 A341420 * A101948 A348484 A087475
KEYWORD
nonn,easy
EXTENSIONS
More terms from Erich Friedman
Definition clarified by Vaclav Kotesovec, Sep 16 2014
STATUS
approved