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

Author

Geoffrey Critzer, Jan 29 2015

Keywords

• nonn

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

Examples

			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)
		

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.

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.

Programs

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 *)

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