A297439 Number of maximum independent vertex sets and minimum vertex covers in the n-web graph.

4, 9, 8, 30, 16, 84, 32, 216, 64, 528, 128, 1248, 256, 2880, 512, 6528, 1024, 14592, 2048, 32256, 4096, 70656, 8192, 153600, 16384, 331776, 32768, 712704, 65536, 1523712, 131072, 3244032, 262144, 6881280, 524288, 14548992, 1048576, 30670848, 2097152

Offset

2,1

Comments

Extended to a(2) using the formula/recurrence.

Links

Table of n, a(n) for n=2..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, Web Graph

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

Formula

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

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

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

Mathematica

Table[If[Mod[n, 2] == 0, 2^(n/2 + 1), 3 2^((n - 3)/2) n], {n, 2, 40}]
LinearRecurrence[{0, 4, 0, -4}, {4, 9, 8, 30}, 20]
CoefficientList[Series[(4 + 9 x - 8 x^2 - 6 x^3)/(-1 + 2 x^2)^2, {x, 0, 20}], x]

Crossrefs

Sequence in context: A345283 A369750 A365780 * A168175 A164382 A145521

Adjacent sequences: A297436 A297437 A297438 * A297440 A297441 A297442

Keyword

nonn,easy

Author

Eric W. Weisstein, Jan 01 2018

Status

approved