cp's OEIS Frontend

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.

%I A254382 #34 Feb 15 2020 11:04:01
%S A254382 0,1,2,3,16,85,696,6349,72080,918873,13484080,219335281,3962458248,
%T A254382 78203547877,1680235050872,38958029188485,970681471597216,
%U A254382 25847378934429361,732794687650764000,22032916968153975769,700360446794528578520
%N 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.
%C A254382 Here, a branching node is a node with at least two children.
%C A254382 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 A254382 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 A254382 Vaclav Kotesovec, <a href="/A254382/b254382.txt">Table of n, a(n) for n = 0..200</a>
%H A254382 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 A254382 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 A254382 E.g.f.: A(x) satisfies 1/(1 - (A(x) - x)) = B(x) where B(x) is the e.g.f. for A231797.
%F A254382 a(n) ~ (1-exp(-1))^(n-1/2) * n^(n-1). - _Vaclav Kotesovec_, Jan 30 2015
%e A254382 a(5) = 85:
%e A254382 ...0................0...............0-o...
%e A254382 ...|.............../ \............ /|\....
%e A254382 ...o..............o   o...........o o o...
%e A254382 ../|\............/ \   ...................
%e A254382 .o o o..........o   o   ..................
%e A254382 These trees have 20 + 60 + 5 = 85 labelings.
%e A254382 From _Gus Wiseman_, Jan 22 2020: (Start)
%e A254382 The a(1) = 1 through a(4) = 16 trees (in the format root[branches]) are:
%e A254382   1  1[2]  1[2,3]  1[2,3,4]
%e A254382      2[1]  2[1,3]  1[2[3,4]]
%e A254382            3[1,2]  1[3[2,4]]
%e A254382                    1[4[2,3]]
%e A254382                    2[1,3,4]
%e A254382                    2[1[3,4]]
%e A254382                    2[3[1,4]]
%e A254382                    2[4[1,3]]
%e A254382                    3[1,2,4]
%e A254382                    3[1[2,4]]
%e A254382                    3[2[1,4]]
%e A254382                    3[4[1,2]]
%e A254382                    4[1,2,3]
%e A254382                    4[1[2,3]]
%e A254382                    4[2[1,3]]
%e A254382                    4[3[1,2]]
%e A254382 (End)
%t A254382 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 A254382 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 A254382 sps[{}]:={{}};sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];
%t A254382 lrt[set_]:=If[Length[set]==0,{},Join@@Table[Apply[root,#]&/@Join@@Table[Tuples[lrt/@stn],{stn,sps[DeleteCases[set,root]]}],{root,set}]];
%t A254382 Table[Length[Select[lrt[Range[n]],FreeQ[Z@@#,_Integer[_]]&]],{n,6}] (* _Gus Wiseman_, Jan 22 2020 *)
%Y A254382 Cf. A231797, A052318 (condition is applied only to leaf nodes).
%Y A254382 The unlabeled version is A198518
%Y A254382 The non-planted case is A060356.
%Y A254382 Labeled rooted trees are A000169.
%Y A254382 Lone-child-avoiding rooted trees are A001678(n + 1).
%Y A254382 Labeled topologically series-reduced rooted trees are A060313.
%Y A254382 Labeled lone-child-avoiding unrooted trees are A108919.
%Y A254382 Cf. A000014, A000669, A001679, A005512, A291636, A331488, A331578.
%K A254382 nonn
%O A254382 0,3
%A A254382 _Geoffrey Critzer_, Jan 29 2015