cp's OEIS Frontend

A245012 The number of labeled caterpillar graphs on n nodes.

%I A245012 #34 Sep 14 2023 03:38:23
%S A245012 1,1,1,3,16,125,1296,15967,225184,3573369,63006400,1222037531,
%T A245012 25856693424,592684459237,14630486811136,386952126342615,
%U A245012 10916525199478336,327220530559545713,10385328804324011136,347921328910693707955,12269256633867840769360
%N A245012 The number of labeled caterpillar graphs on n nodes.
%C A245012 All trees of order less than 7 are caterpillars so for 0 <= n < 7, a(n) = n^(n-2) = A000272(n).
%C A245012 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 A245012 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CaterpillarGraph.html">Caterpillar Graph</a>
%F A245012 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 A245012 a(7) = 15967 because there is only one unlabeled tree that is not a caterpillar (Cf. A052471):
%e A245012 o-o-o-o-o
%e A245012     |
%e A245012     o
%e A245012     |
%e A245012     o
%e A245012 This tree has 840 labelings. So 7^5 - 840 = 15967.
%t A245012 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 A245012 (PARI) N=33;  x='x+O('x^N);
%o A245012 A = x *exp(x);  C = A - x;
%o A245012 egf = C - x^2/2! + x + 1 + sum(k=0, N, A^k*C^2/2);
%o A245012 Vec(serlaplace(egf))
%o A245012 \\ _Joerg Arndt_, Jul 10 2014
%Y A245012 Cf. A005418.
%K A245012 nonn
%O A245012 0,4
%A A245012 _Geoffrey Critzer_, Jul 09 2014