A254382 - OEIS

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

(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.