%I #28 Feb 16 2025 08:33:20
%S 17,80,388,1872,9040,43648,210752,1017600,4913408,23724032,114549760,
%T 553095168,2670579712,12894699520,62261116928,300623265792,
%U 1451537530880,7008643186688,33840722870272,163397464227840,788952748392448,3809400850481152
%N a(1) = 17, a(2) = 80, a(n) = 4*(a(n-1) + a(n-2)) for n >= 3.
%C 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.
%C Also the number of independent vertex sets of the n-alkane graph. - _Eric W. Weisstein_, Jul 15 2021
%D R. E. Merrifield, H. E. Simmons, Topological Methods in Chemistry, Wiley, New York, 1989. pp. 161-162.
%H H. Prodinger and R. F. Tichy, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/20-1/prodinger.pdf">Fibonacci numbers of graphs</a>, Fibonacci Quarterly, 20, 1982, 16-21.
%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/AlkaneGraph.html">Alkane Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/MaximumIndependentEdgeSet.html">Maximum Independent Edge Set</a>
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (4,4).
%F a(n) = (1/8)*(12-11*sqrt(2))*(2-2*sqrt(2))^n + (1/8)*(12+11*sqrt(2))*(2+2*sqrt(2))^n.
%F G.f.: x*(17+12*x)/(1-4*x-4*x^2).
%p 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);
%t LinearRecurrence[{4, 4}, {17, 80}, 20] (* _Eric W. Weisstein_, Jul 15 2021 *)
%t CoefficientList[Series[(17 + 12 x)/(1 - 4 x - 4 x^2), {x, 0, 20}], x] (* _Eric W. Weisstein_, Jul 15 2021 *)
%t 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 *)
%K nonn,easy,changed
%O 1,1
%A _Emeric Deutsch_, Oct 30 2013