A392620 Number of maximal independent vertex sets in the n-necklace graph.

4, 10, 34, 114, 374, 1222, 3994, 13058, 42694, 139590, 456394, 1492194, 4878774, 15951302, 52153274, 170516738, 557509734, 1822795270, 5959685354, 19485375074, 63708034774, 208295384582, 681028184154, 2226642652418, 7280076826374, 23802435716550, 77822797691914

Offset

1,1

Links

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

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

Eric Weisstein's World of Mathematics, Necklace Graph.

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

Formula

a(n) = 4*a(n-1)-3*a(n-2)+2*a(n-3).

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

Mathematica

Table[RootSum[-2 + 3 # - 4 #^2 + #^3 &, #^n &], {n, 20}]
RootSum[-2 + 3 # - 4 #^2 + #^3 &, #^Range[20] &]
LinearRecurrence[{4, -3, 2}, {4, 10, 34}, 20]
CoefficientList[Series[-2 (2 - 3 x + 3 x^2)/(-1 + 4 x - 3 x^2 + 2 x^3), {x, 0, 20}], x]

Crossrefs

Sequence in context: A231524 A182645 A006343 * A149173 A149174 A283070

Adjacent sequences: A392617 A392618 A392619 * A392621 A392622 A392623

Keyword

nonn,easy

Author

Eric W. Weisstein, Feb 15 2026

Status

approved