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.

0, 1, 2, 3, 16, 85, 696, 6349, 72080, 918873, 13484080, 219335281, 3962458248, 78203547877, 1680235050872, 38958029188485, 970681471597216, 25847378934429361, 732794687650764000, 22032916968153975769, 700360446794528578520

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: A007118 A012572 A371613 * A354610 A067848 A269067

Adjacent sequences: A254379 A254380 A254381 * A254383 A254384 A254385

Keyword

nonn

Author

Geoffrey Critzer, Jan 29 2015

Status

approved