login
Number of nonisomorphic spanning trees of the triangular snake nC_3.
2

%I #24 Oct 17 2024 20:06:35

%S 1,3,7,21,57,171,495,1485,4401,13203,39447,118341,354537,1063611,

%T 3189375,9568125,28700001,86100003,258286887,774860661,2324542617,

%U 6973627851,20920765455,62762296365,188286534801,564859604403,1694577750327,5083733250981,15251196564297,45753589692891

%N Number of nonisomorphic spanning trees of the triangular snake nC_3.

%C 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.

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

%H Paolo Xausa, <a href="/A374721/b374721.txt">Table of n, a(n) for n = 1..1000</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/TriangularSnakeGraph.html">Triangular Snake Graph</a>.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,3,-9).

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

%F From _Stefano Spezia_, Jul 20 2024: (Start)

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

%F 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)

%e For n=2 the a(2)=3 nonisomorphic spanning trees of 2C_3-snake are:

%e __ __ __ __, __\__ __, __\/__

%t A374721[n_] := 2*3^(n - 2) + 3^Floor[(n - 2)/2]; Array[A374721, 30] (* or *)

%t LinearRecurrence[{3, 3, -9}, {1, 3, 7}, 30] (* _Paolo Xausa_, Oct 17 2024 *)

%Y Cf. A374722.

%K nonn,easy

%O 1,2

%A _Christian Barrientos_, Jul 17 2024