%I #34 Sep 14 2023 03:38:23

%S 1,1,1,3,16,125,1296,15967,225184,3573369,63006400,1222037531,

%T 25856693424,592684459237,14630486811136,386952126342615,

%U 10916525199478336,327220530559545713,10385328804324011136,347921328910693707955,12269256633867840769360

%N The number of labeled caterpillar graphs on n nodes.

%C All trees of order less than 7 are caterpillars so for 0 <= n < 7, a(n) = n^(n-2) = A000272(n).

%C Call a rooted labeled tree of height at most one a short tree. A caterpillar is a single short tree or a succession of short trees sandwiched between two nontrivial short trees. - _Geoffrey Critzer_, Aug 03 2016

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

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

%e a(7) = 15967 because there is only one unlabeled tree that is not a caterpillar (Cf. A052471):

%e o-o-o-o-o

%e |

%e o

%e |

%e o

%e This tree has 840 labelings. So 7^5 - 840 = 15967.

%t 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]

%o (PARI) N=33; x='x+O('x^N);

%o A = x *exp(x); C = A - x;

%o egf = C - x^2/2! + x + 1 + sum(k=0, N, A^k*C^2/2);

%o Vec(serlaplace(egf))

%o \\ _Joerg Arndt_, Jul 10 2014

%Y Cf. A005418.

%K nonn

%O 0,4

%A _Geoffrey Critzer_, Jul 09 2014