|
|
A374723
|
|
Number of nonisomorphic spanning trees of the nC_4-snake where the distance between cutpoints is 1.
|
|
2
|
|
|
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
(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 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
|
|
|
FORMULA
|
a(n) = 2*4^(n-2) + 4^floor((n-1)/2) for n > 1.
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
|
|
|
KEYWORD
|
easy,nonn,new
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|