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!)
A254382 Number of rooted labeled trees on n nodes such that every nonroot node is the child of a branching node or of the root. 7
0, 1, 2, 3, 16, 85, 696, 6349, 72080, 918873, 13484080, 219335281, 3962458248, 78203547877, 1680235050872, 38958029188485, 970681471597216, 25847378934429361, 732794687650764000, 22032916968153975769, 700360446794528578520 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Here, a branching node is a node with at least two children.

In other words, a(n) is the number of labeled rooted trees on n nodes such that the path from every node towards the root reaches a branching node (or the root) in one step.

Also labeled rooted trees that are lone-child-avoiding except possibly for the root. The unlabeled version is A198518. - Gus Wiseman, Jan 22 2020

LINKS

Vaclav Kotesovec, Table of n, a(n) for n = 0..200

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

E.g.f.: A(x) satisfies 1/(1 - (A(x) - x)) = B(x) where B(x) is the e.g.f. for A231797.

a(n) ~ (1-exp(-1))^(n-1/2) * n^(n-1). - Vaclav Kotesovec, Jan 30 2015

EXAMPLE

a(5) = 85:

...0................0...............0-o...

...|.............../ \............ /|\....

...o..............o   o...........o o o...

../|\............/ \   ...................

.o o o..........o   o   ..................

These trees have 20 + 60 + 5 = 85 labelings.

From Gus Wiseman, Jan 22 2020: (Start)

The a(1) = 1 through a(4) = 16 trees (in the format root[branches]) are:

  1  1[2]  1[2,3]  1[2,3,4]

     2[1]  2[1,3]  1[2[3,4]]

           3[1,2]  1[3[2,4]]

                   1[4[2,3]]

                   2[1,3,4]

                   2[1[3,4]]

                   2[3[1,4]]

                   2[4[1,3]]

                   3[1,2,4]

                   3[1[2,4]]

                   3[2[1,4]]

                   3[4[1,2]]

                   4[1,2,3]

                   4[1[2,3]]

                   4[2[1,3]]

                   4[3[1,2]]

(End)

MATHEMATICA

nn = 20; b = 1 + Sum[nn = n; n! Coefficient[Series[(Exp[x] - x)^n, {x, 0, nn}], x^n]*x^n/n!, {n, 1, nn}]; c = Sum[a[n] x^n/n!, {n, 0, nn}]; sol = SolveAlways[b == Series[1/(1 - (c - x)), {x, 0, nn}], x]; Flatten[Table[a[n], {n, 0, nn}] /. sol]

nn = 30; CoefficientList[Series[1+x-1/Sum[SeriesCoefficient[(E^x-x)^n, {x, 0, n}]*x^n, {n, 0, nn}], {x, 0, nn}], x] * Range[0, nn]! (* Vaclav Kotesovec, Jan 30 2015 *)

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

lrt[set_]:=If[Length[set]==0, {}, Join@@Table[Apply[root, #]&/@Join@@Table[Tuples[lrt/@stn], {stn, sps[DeleteCases[set, root]]}], {root, set}]];

Table[Length[Select[lrt[Range[n]], FreeQ[Z@@#, _Integer[_]]&]], {n, 6}] (* Gus Wiseman, Jan 22 2020 *)

CROSSREFS

Cf. A231797, A052318 (condition is applied only to leaf nodes).

The unlabeled version is A198518

The non-planted case is A060356.

Labeled rooted trees are A000169.

Lone-child-avoiding rooted trees are A001678(n + 1).

Labeled topologically series-reduced rooted trees are A060313.

Labeled lone-child-avoiding unrooted trees are A108919.

Cf. A000014, A000669, A001679, A005512, A291636, A331488, A331578.

Sequence in context: A073997 A007118 A012572 * A067848 A269067 A139802

Adjacent sequences:  A254379 A254380 A254381 * A254383 A254384 A254385

KEYWORD

nonn

AUTHOR

Geoffrey Critzer, Jan 29 2015

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 July 5 04:19 EDT 2020. Contains 335459 sequences. (Running on oeis4.)