A374723 Number of nonisomorphic spanning trees of the nC_4-snake where the distance between cutpoints is 1.

1, 3, 12, 36, 144, 528, 2112, 8256, 33024, 131328, 525312, 2098176, 8392704, 33558528, 134234112, 536887296, 2147549184, 8590000128, 34360000512, 137439215616, 549756862464, 2199024304128, 8796097216512, 35184376283136, 140737505132544, 562949970198528, 2251799880794112, 9007199321849856, 36028797287399424, 144115188344291328

Offset

1,2

Comments

a(n) is the number of spanning trees of the cyclic snake formed with n copies of the cycle on 4 vertices and distance 1 between cutpoints. A cyclic snake is a connected graph whose block-cutpoint is a path and all its n blocks are isomorphic to the cycle C_m.

References

Christian Barrientos, Graceful labelings of cyclic snakes, Ars Combin., 60 (2001), 85-96.

Links

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

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

Formula

a(n) = 2*4^(n-2) + 4^floor((n-1)/2) for n > 1.

From Stefano Spezia, Jul 20 2024: (Start)

G.f.: x*(1 - x - 4*x^2 - 8*x^3)/((1 - 2*x)*(1 + 2*x)*(1 - 4*x)).

E.g.f.: (2*cosh(2*x) + 4*sinh(2*x) + exp(4*x) - 4*x - 3)/8. (End)

Example

For n=2, a(2)=3 because there are 3 spanning trees of 2C_4-snake
__ __ __ __ __ __, __ __ __|__ __, __ __\/__ __

Mathematica

Drop[CoefficientList[Series[x*(1 - x - 4*x^2 - 8*x^3)/((1 - 2*x)*(1 + 2*x)*(1 - 4*x)), {x, 0, 30}], x], 1] (* Georg Fischer, Aug 09 2024 *)

Prog

(PARI) for(n=1, 30, print1(if(n==1, 1, 2*4^(n-2) + 4^floor((n-1)/2)), ", ")) \\ Georg Fischer, Aug 09 2024

Crossrefs

Cf. A374721, A374722.

Sequence in context: A155714 A282022 A004661 * A074430 A064028 A326241

Adjacent sequences: A374720 A374721 A374722 * A374724 A374725 A374726

Keyword

easy,nonn,new

Author

Christian Barrientos, Jul 17 2024

Extensions

a(27)-a(30) corrected by Georg Fischer, Aug 09 2024

Status

approved