OFFSET
0,4
COMMENTS
All trees of order less than 7 are caterpillars so for 0 <= n < 7, a(n) = n^(n-2) = A000272(n).
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
LINKS
Eric Weisstein's World of Mathematics, Caterpillar Graph
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.
EXAMPLE
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.
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]
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
Geoffrey Critzer, Jul 09 2014
STATUS
approved