A289203 Number of maximum independent vertex sets in the n X n knight graph.

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

Author

Eric W. Weisstein, Jun 28 2017

Keywords

• nonn
• easy

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

Crossrefs

Cf. A000034.

Programs

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]

Python

def A289203(n): return (1,1,2,6)[n-1] if n<5 else 2-(n&1) # Chai Wah Wu, Feb 12 2024

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