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

Links

Table of n, a(n) for n=1..92.

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

Cf. A000034.

Sequence in context: A024573 A191359 A339766 * A246505 A302551 A078434

Adjacent sequences: A289200 A289201 A289202 * A289204 A289205 A289206

Keyword

nonn,easy

Author

Eric W. Weisstein, Jun 28 2017

Status

approved