login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A245012 The number of labeled caterpillar graphs on n nodes. 0
1, 1, 1, 3, 16, 125, 1296, 15967, 225184, 3573369, 63006400, 1222037531, 25856693424, 592684459237, 14630486811136, 386952126342615, 10916525199478336, 327220530559545713, 10385328804324011136, 347921328910693707955, 12269256633867840769360 (list; graph; refs; listen; history; text; internal format)
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

Table of n, a(n) for n=0..20.

Eric Weisstein's World of Mathematics, Caterpillar

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

Cf. A005418.

Sequence in context: A188417 A157457 A000950 * A000951 A000272 A246527

Adjacent sequences:  A245009 A245010 A245011 * A245013 A245014 A245015

KEYWORD

nonn

AUTHOR

Geoffrey Critzer, Jul 09 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 24 12:35 EST 2018. Contains 299623 sequences. (Running on oeis4.)