A030978 Maximal number of non-attacking knights on an n X n board.

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

Author

Eric W. Weisstein

Keywords

• nonn
• easy

Comments

In other words, independence number of the n X n knight graph. - Eric W. Weisstein, May 05 2017

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
• V. 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
• Index entries for linear recurrences with constant coefficients, signature (2,0,-2,1).

Crossrefs

Agrees with A000982 for n>1.

Cf. A244081.

Programs

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

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]

Extensions

More terms from Erich Friedman

Definition clarified by Vaclav Kotesovec, Sep 16 2014