A287350 Number of independent vertex sets and vertex covers in the n-gear graph.

5, 11, 26, 63, 155, 386, 971, 2463, 6290, 16151, 41651, 107778, 279635, 727031, 1893266, 4936383, 12883115, 33647426, 87928091, 229874703, 601171730, 1572591911, 4114506851, 10766734338, 28177307555, 73748411111, 193034371346, 505287594063, 1322694193115

Offset

1,1

Comments

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

Links

Colin Barker, Table of n, a(n) for n = 1..1000

Eric Weisstein's World of Mathematics, Gear Graph

Eric Weisstein's World of Mathematics, Independent Vertex Set

Eric Weisstein's World of Mathematics, Vertex Cover

Index entries for linear recurrences with constant coefficients, signature (5,-7,2).

Formula

a(n) = 2^n + Lucas(2*n).

G.f.: x*(5 - 14*x + 6*x^2)/((1 - 2*x)*(1 - 3*x + x^2)). - Ilya Gutkovskiy, May 23 2017

From Colin Barker, Jun 05 2017: (Start)

a(n) = 5*a(n-1) - 7*a(n-2) + 2*a(n-3) for n>3.

a(n) = 2^(-n)*(4^n + (3-sqrt(5))^n + (3+sqrt(5))^n).

(End)

Mathematica

Table[2^n + LucasL[2 n], {n, 20}]
LinearRecurrence[{5, -7, 2}, {5, 11, 26}, 20]
CoefficientList[Series[(-5 + 14 x - 6 x^2)/(-1 + 5 x - 7 x^2 + 2 x^3), {x, 0, 20}], x]

Prog

(Python)
from sympy import lucas
def a(n): return 2**n + lucas(2*n) # Indranil Ghosh, May 24 2017
(PARI) Vec(x*(5 - 14*x + 6*x^2)/((1 - 2*x)*(1 - 3*x + x^2)) + O(x^30)) \\ Colin Barker, Jun 05 2017

Crossrefs

Cf. A000032, A000079, A005248.

Sequence in context: A354838 A038253 A274681 * A294091 A032379 A152535

Adjacent sequences: A287347 A287348 A287349 * A287351 A287352 A287353

Keyword

nonn,easy

Author

Eric W. Weisstein, May 23 2017

Status

approved