A393464 Number of maximum independent vertex sets and minimum vertex covers in the n-necklace graph.

4, 4, 24, 8, 80, 16, 224, 32, 576, 64, 1408, 128, 3328, 256, 7680, 512, 17408, 1024, 38912, 2048, 86016, 4096, 188416, 8192, 409600, 16384, 884736, 32768, 1900544, 65536, 4063232, 131072, 8650752, 262144, 18350080, 524288, 38797312, 1048576, 81788928, 2097152

Offset

1,1

Links

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

Eric Weisstein's World of Mathematics, Maximum Independent Vertex Set.

Eric Weisstein's World of Mathematics, Minimum Vertex Cover.

Eric Weisstein's World of Mathematics, Necklace Graph.

Index entries for linear recurrences with constant coefficients, signature (0,4,0,-4).

Formula

a(n) = 4*a(n-2)-4*a(n-4).

G.f.: -4*x*(-1-x-2*x^2+2*x^3)/(-1+2*x^2)^2.

Mathematica

Table[2^(n/2) (1 + (-1)^n - Sqrt[2] (-1 + (-1)^n) n), {n, 20}]
LinearRecurrence[{0, 4, 0, -4}, {4, 4, 24, 8}, 20]
CoefficientList[Series[-4 (-1 - x - 2 x^2 + 2 x^3)/(-1 + 2 x^2)^2, {x, 0, 20}], x]

Crossrefs

Sequence in context: A271155 A271132 A270456 * A088304 A131978 A049614

Adjacent sequences: A393461 A393462 A393463 * A393465 A393466 A393467

Keyword

nonn,easy

Author

Eric W. Weisstein, Feb 15 2026

Status

approved