A374721 Number of nonisomorphic spanning trees of the triangular snake nC_3.

1, 3, 7, 21, 57, 171, 495, 1485, 4401, 13203, 39447, 118341, 354537, 1063611, 3189375, 9568125, 28700001, 86100003, 258286887, 774860661, 2324542617, 6973627851, 20920765455, 62762296365, 188286534801, 564859604403, 1694577750327, 5083733250981, 15251196564297, 45753589692891

Offset

1,2

Comments

a(n) is the number of spanning trees of the cyclic snake formed with n copies of the cycle on 3 vertices. 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

Paolo Xausa, Table of n, a(n) for n = 1..1000

Eric Weisstein's World of Mathematics, Triangular Snake Graph.

Index entries for linear recurrences with constant coefficients, signature (3,3,-9).

Formula

a(n) = 2*3^(n-2) + 3^floor((n-2)/2).

From Stefano Spezia, Jul 20 2024: (Start)

G.f.: x*(1 - 5*x^2)/((1 - 3*x)*(1 - 3*x^2)).

E.g.f.: (2*cosh(3*x) + 3*cosh(sqrt(3)*x) + 2*sinh(3*x) + sqrt(3)*sinh(sqrt(3)*x) - 5)/9. (End)

Example

For n=2 the a(2)=3 nonisomorphic spanning trees of 2C_3-snake are:
__ __ __ __, __\__ __, __\/__

Mathematica

A374721[n_] := 2*3^(n - 2) + 3^Floor[(n - 2)/2]; Array[A374721, 30] (* or *)
LinearRecurrence[{3, 3, -9}, {1, 3, 7}, 30] (* Paolo Xausa, Oct 17 2024 *)

Crossrefs

Cf. A374722.

Sequence in context: A320803 A262184 A091489 * A375016 A104779 A178718

Adjacent sequences: A374718 A374719 A374720 * A374722 A374723 A374724

Keyword

nonn,easy,changed

Author

Christian Barrientos, Jul 17 2024

Status

approved