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
Index entries for linear recurrences with constant coefficients, signature (0,1).
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
KEYWORD
nonn,easy
AUTHOR
Eric W. Weisstein, Jun 28 2017
STATUS
approved