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