Voozh

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

(list; graph; refs; listen; history; text; internal format)

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