A228602 a(1) = 17, a(2) = 80, a(n) = 4*(a(n-1) + a(n-2)) for n >= 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

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

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

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

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

Adjacent sequences: A228599 A228600 A228601 * A228603 A228604 A228605

Keyword

nonn,easy

Author

Emeric Deutsch, Oct 30 2013

Status

approved