login
A287350
Number of independent vertex sets and vertex covers in the n-gear graph.
1
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
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
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
KEYWORD
nonn,easy
AUTHOR
Eric W. Weisstein, May 23 2017
STATUS
approved