login
A289203
Number of maximum independent vertex sets in the n X n knight graph.
2
1, 1, 2, 6, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2
OFFSET
1,3
LINKS
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, Knight Graph
Eric Weisstein's World of Mathematics, Maximum Independent Vertex Set
FORMULA
For n > 4, a(n) = ((-1)^n + 3)/2.
G.f.: (x*(-1 - x - x^2 - 5*x^3 + x^4 + 4*x^5))/(-1 + x^2).
MATHEMATICA
Table[Length[With[{g = KnightTourGraph[n, n]}, FindIndependentVertexSet[g, Length /@ FindIndependentVertexSet[g], All]]], {n, 8}]
Table[Piecewise[{{1, n == 2}, {2, n == 3}, {6, n == 4}, {2, Mod[n, 2] == 0}, {1, Mod[n, 2] == 1}}], {n, 100}]
Table[Piecewise[{{1, n == 2}, {2, n == 3}, {6, n == 4}}, ((-1)^n + 3)/2], {n, 100}]
CoefficientList[Series[(-1 - x - x^2 - 5 x^3 + x^4 + 4 x^5)/(-1 + x^2), {x, 0, 20}], x]
PROG
(Python)
def A289203(n): return (1, 1, 2, 6)[n-1] if n<5 else 2-(n&1) # Chai Wah Wu, Feb 12 2024
CROSSREFS
Cf. A000034.
Sequence in context: A024573 A191359 A339766 * A246505 A302551 A078434
KEYWORD
nonn,easy
AUTHOR
Eric W. Weisstein, Jun 28 2017
STATUS
approved