%I #34 Feb 15 2020 11:04:01

%S 0,1,2,3,16,85,696,6349,72080,918873,13484080,219335281,3962458248,

%T 78203547877,1680235050872,38958029188485,970681471597216,

%U 25847378934429361,732794687650764000,22032916968153975769,700360446794528578520

%N Number of rooted labeled trees on n nodes such that every nonroot node is the child of a branching node or of the root.

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

%C 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.

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

%H Vaclav Kotesovec, <a href="/A254382/b254382.txt">Table of n, a(n) for n = 0..200</a>

%H David Callan, <a href="http://arxiv.org/abs/1406.7784">A sign-reversing involution to count labeled lone-child-avoiding trees</a>, arXiv:1406.7784 [math.CO], (30-June-2014).

%H Gus Wiseman, <a href="https://docs.google.com/document/d/e/2PACX-1vS1zCO9fgAIe5rGiAhTtlrOTuqsmuPos2zkeFPYB80gNzLb44ufqIqksTB4uM9SIpwlvo-oOHhepywy/pub">Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.</a>

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

%F a(n) ~ (1-exp(-1))^(n-1/2) * n^(n-1). - _Vaclav Kotesovec_, Jan 30 2015

%e a(5) = 85:

%e ...0................0...............0-o...

%e ...|.............../ \............ /|\....

%e ...o..............o o...........o o o...

%e ../|\............/ \ ...................

%e .o o o..........o o ..................

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

%e From _Gus Wiseman_, Jan 22 2020: (Start)

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

%e 1 1[2] 1[2,3] 1[2,3,4]

%e 2[1] 2[1,3] 1[2[3,4]]

%e 3[1,2] 1[3[2,4]]

%e 1[4[2,3]]

%e 2[1,3,4]

%e 2[1[3,4]]

%e 2[3[1,4]]

%e 2[4[1,3]]

%e 3[1,2,4]

%e 3[1[2,4]]

%e 3[2[1,4]]

%e 3[4[1,2]]

%e 4[1,2,3]

%e 4[1[2,3]]

%e 4[2[1,3]]

%e 4[3[1,2]]

%e (End)

%t 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]

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

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

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

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

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

%Y The unlabeled version is A198518

%Y The non-planted case is A060356.

%Y Labeled rooted trees are A000169.

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

%Y Labeled topologically series-reduced rooted trees are A060313.

%Y Labeled lone-child-avoiding unrooted trees are A108919.

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

%K nonn

%O 0,3

%A _Geoffrey Critzer_, Jan 29 2015