login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A060356 Expansion of e.g.f.: -LambertW(-x/(1+x)). 25
0, 1, 0, 3, 4, 65, 306, 4207, 38424, 573057, 7753510, 134046671, 2353898196, 47602871329, 1013794852266, 23751106404495, 590663769125296, 15806094859299329, 448284980183376078, 13515502344669830287 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

Also the number of labeled lone-child-avoiding rooted trees with n nodes. A rooted tree is lone-child-avoiding if it has no unary branchings, meaning every non-leaf node covers at least two other nodes. The unlabeled version is A001678(n + 1). - Gus Wiseman, Jan 20 2020

LINKS

Harry J. Smith, Table of n, a(n) for n = 0..100

David Callan, A sign-reversing involution to count labeled lone-child-avoiding trees, arXiv:1406.7784 [math.CO], (30-June-2014)

Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.

FORMULA

a(n) = Sum_{k=1..n} (-1)^(n-k)*n!/k!*binomial(n-1, k-1)*k^(k-1). a(n) = Sum_{k=0..n} Stirling1(n, k)*A058863(k). - Vladeta Jovovic, Sep 17 2003

a(n) ~ n^(n-1) * (1-exp(-1))^(n+1/2). - Vaclav Kotesovec, Nov 27 2012

a(n) = n * A108919(n). - Gus Wiseman, Dec 31 2019

EXAMPLE

From Gus Wiseman, Dec 31 2019: (Start)

Non-isomorphic representatives of the a(7) = 4207 trees, written as root[branches], are:

  1[2,3[4,5[6,7]]]

  1[2,3[4,5,6,7]]

  1[2[3,4],5[6,7]]

  1[2,3,4[5,6,7]]

  1[2,3,4,5[6,7]]

  1[2,3,4,5,6,7]

(End)

MATHEMATICA

CoefficientList[Series[-LambertW[-x/(1+x)], {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Nov 27 2012 *)

sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];

a[n_]:=If[n==1, 1, n*Sum[Times@@a/@Length/@stn, {stn, Select[sps[Range[n-1]], Length[#]>1&]}]];

Array[a, 10] (* Gus Wiseman, Dec 31 2019 *)

PROG

(PARI) { for (n=0, 100, f=n!; a=sum(k=1, n, (-1)^(n - k)*f/k!*binomial(n - 1, k - 1)*k^(k - 1)); write("b060356.txt", n, " ", a); ) } \\ Harry J. Smith, Jul 04 2009

(PARI) x='x+O('x^30); concat([0], Vec(serlaplace(-lambertw(-x/(1+x))))) \\ G. C. Greubel, Feb 19 2018

(GAP) List([0..20], n->Sum([1..n], k->(-1)^(n-k)*Factorial(n)/Factorial(k)*Binomial(n-1, k-1)*k^(k-1))); # Muniru A Asiru, Feb 19 2018

CROSSREFS

Cf. A052871, A060313.

Cf. A008297.

Column k=0 of A231602.

The unlabeled version is A001678(n + 1).

The case where the root is fixed is A108919.

Unlabeled rooted trees are counted by A000081.

Lone-child-avoiding rooted trees with labeled leaves are A000311.

Matula-Goebel numbers of lone-child-avoiding rooted trees are A291636.

Singleton-reduced rooted trees are counted by A330951.

Cf. A000669, A004111, A005121, A048816, A292504, A316651, A316652, A318231, A318813, A330465, A330624.

Sequence in context: A278035 A079076 A274699 * A052323 A012087 A012194

Adjacent sequences:  A060353 A060354 A060355 * A060357 A060358 A060359

KEYWORD

easy,nonn

AUTHOR

Vladeta Jovovic, Apr 01 2001

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 18 15:30 EST 2020. Contains 332019 sequences. (Running on oeis4.)