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,3

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

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]

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

Cf. A244081.

Sequence in context: A133940 A174398 A341420 * A101948 A348484 A087475

Adjacent sequences: A030975 A030976 A030977 * A030979 A030980 A030981

Keyword

nonn,easy

Author

Eric W. Weisstein

Extensions

More terms from Erich Friedman

Definition clarified by Vaclav Kotesovec, Sep 16 2014

Status

approved