A245012 The number of labeled caterpillar graphs on n nodes.
1, 1, 1, 3, 16, 125, 1296, 15967, 225184, 3573369, 63006400, 1222037531, 25856693424, 592684459237, 14630486811136, 386952126342615, 10916525199478336, 327220530559545713, 10385328804324011136, 347921328910693707955, 12269256633867840769360
Offset: 0
Keywords
Examples
a(7) = 15967 because there is only one unlabeled tree that is not a caterpillar (Cf. A052471):
o-o-o-o-o
|
o
|
o
This tree has 840 labelings. So 7^5 - 840 = 15967.
Links
- Eric Weisstein's World of Mathematics, Caterpillar Graph
Crossrefs
Cf. A005418.
Programs
-
Mathematica
nn=20;a=x Exp[x];c=a-x;Range[0,nn]!CoefficientList[Series[c-x^2/2!+x+1+Sum[a^k c^2/2,{k,0,nn}],{x,0,nn}],x] -
PARI
N=33; x='x+O('x^N); A = x *exp(x); C = A - x; egf = C - x^2/2! + x + 1 + sum(k=0, N, A^k*C^2/2); Vec(serlaplace(egf)) \\ Joerg Arndt, Jul 10 2014
Formula
E.g.f.: C(x) - x^2/2! + x + 1 + Sum_{k>=0} A(x)^k*C(x)^2/2, where A(x) = x*exp(x) and C(x) = A(x) - x.
Comments