|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
| |
|
|
