login
A228602
a(1) = 17, a(2) = 80, a(n) = 4*(a(n-1) + a(n-2)) for n >= 3.
3
17, 80, 388, 1872, 9040, 43648, 210752, 1017600, 4913408, 23724032, 114549760, 553095168, 2670579712, 12894699520, 62261116928, 300623265792, 1451537530880, 7008643186688, 33840722870272, 163397464227840, 788952748392448, 3809400850481152
OFFSET
1,1
COMMENTS
The Merrifield-Simmons index of the caterpillar tree whose carbon skeleton is the path tree P_n (i.e. path tree P_{n+2} with two pendant edges attached to each non-leaf vertex). Example: for n=1 the path tree has 1 vertex, the associated caterpillar tree is the star tree with 5 vertices; it is easy to see that we have 1, 5, 6, 4, 1 independent vertex subsets with 0, 1, 2, 3, 4 vertices, respectively; 1+5+6+4+1 = 17.
Also the number of independent vertex sets of the n-alkane graph. - Eric W. Weisstein, Jul 15 2021
REFERENCES
R. E. Merrifield, H. E. Simmons, Topological Methods in Chemistry, Wiley, New York, 1989. pp. 161-162.
LINKS
H. Prodinger and R. F. Tichy, Fibonacci numbers of graphs, Fibonacci Quarterly, 20, 1982, 16-21.
Eric Weisstein's World of Mathematics, Alkane Graph
Eric Weisstein's World of Mathematics, Maximum Independent Edge Set
FORMULA
a(n) = (1/8)*(12-11*sqrt(2))*(2-2*sqrt(2))^n + (1/8)*(12+11*sqrt(2))*(2+2*sqrt(2))^n.
G.f.: x*(17+12*x)/(1-4*x-4*x^2).
MAPLE
a := proc (n) if n = 1 then 17 elif n = 2 then 80 else 4*a(n-1)+4*a(n-2) end if end proc: seq(a(n), n = 1 .. 25);
MATHEMATICA
LinearRecurrence[{4, 4}, {17, 80}, 20] (* Eric W. Weisstein, Jul 15 2021 *)
CoefficientList[Series[(17 + 12 x)/(1 - 4 x - 4 x^2), {x, 0, 20}], x] (* Eric W. Weisstein, Jul 15 2021 *)
Table[((12 - 11 Sqrt[2]) (2 - 2 Sqrt[2])^n + (2 (1 + Sqrt[2]))^n (12 + 11 Sqrt[2]))/8, {n, 20}] // Expand (* Eric W. Weisstein, Jul 15 2021 *)
CROSSREFS
Sequence in context: A172045 A338549 A060934 * A100688 A044204 A044585
KEYWORD
nonn,easy
AUTHOR
Emeric Deutsch, Oct 30 2013
STATUS
approved