A055541 Total number of leaves (nodes of vertex degree 1) in all labeled trees with n nodes.

0, 2, 6, 36, 320, 3750, 54432, 941192, 18874368, 430467210, 11000000000, 311249095212, 9659108818944, 326173191714734, 11905721598812160, 467086816406250000, 19599665578316398592, 875901453762003632658, 41532319635035234107392, 2082547005958224830656820

Offset

1,2

Comments

Equivalently, a(n) is the number of rooted labeled trees such that the root node has degree 1. - Geoffrey Critzer, Feb 07 2012

Links

G. C. Greubel, Table of n, a(n) for n = 1..385

Dixy Msapato, Counting the number of tau-exceptional sequences over Nakayama algebras, arXiv:2002.12194 [math.RT], 2020.

Eric Weisstein's World of Mathematics, Tree Leaf.

Index entries for sequences related to trees

Formula

From Vladeta Jovovic, Mar 31 2001: (Start)

a(n) = n*(n-1)^(n-2), n > 1.

E.g.f.: -x*LambertW(-x). (End)

a(n) = Sum_{k=1..n} (A055314(n, k)*k). - Christian G. Bower, Jun 12 2000

E.g.f.: x*T(x) where T(x) is the e.g.f. for A000169. - Geoffrey Critzer, Feb 07 2012

Mathematica

Join[{0, 2}, Table[Sum[n!/k! StirlingS2[n-2, n-k] k, {k, 2, n-1}], {n, 3, 20}]] (* Geoffrey Critzer, Nov 22 2011 *)
Join[{0, 2}, Table[n*(n-1)^(n-2), {n, 3, 50}]] (* or *) Rest[With[{nmax = 40}, CoefficientList[Series[-x*LambertW[-x], {x, 0, nmax}], x]*Range[0, nmax]!]] (* G. C. Greubel, Nov 11 2017 *)

Prog

(PARI) for(n=1, 30, print1(if(n==1, 0, if(n==2, 2, n*(n-1)^(n-2))), ", ")) \\ G. C. Greubel, Nov 11 2017
(Magma) [0, 2] cat [n*(n-1)^(n-2): n in [3..10]]; // G. C. Greubel, Nov 11 2017

Crossrefs

Cf. A003227, A003228, A055314, A055540, A055897.

Essentially the same as A061302.

Sequence in context: A182037 A306066 A061302 * A275551 A321085 A133822

Adjacent sequences: A055538 A055539 A055540 * A055542 A055543 A055544

Keyword

nonn

Author

Eric W. Weisstein

Extensions

More terms from Christian G. Bower, Jun 12 2000

Status

approved