cp's OEIS Frontend

A331578 Number of labeled series-reduced rooted trees with n vertices and more than two branches of the root.

%I A331578 #20 Dec 19 2024 23:40:54
%S A331578 0,0,0,4,5,186,847,17928,166833,3196630,45667391,925287276,
%T A331578 17407857337,393376875906,8989368580935,229332484742416,
%U A331578 6094576250570849,174924522900914094,5271210321949744111,168792243040279327860,5674164658298121248361,200870558472768096534490
%N A331578 Number of labeled series-reduced rooted trees with n vertices and more than two branches of the root.
%C A331578 A rooted tree is series-reduced if no vertex (including the root) has degree 2.
%C A331578 Also labeled lone-child-avoiding rooted trees with n vertices and more than two branches, where a rooted tree is lone-child-avoiding if no vertex has exactly one child.
%H A331578 Andrew Howroyd, <a href="/A331578/b331578.txt">Table of n, a(n) for n = 1..200</a>
%F A331578 From _Andrew Howroyd_, Dec 09 2020: (Start)
%F A331578 a(n) = A060313(n) - n*A060356(n-1) for n > 1.
%F A331578 a(n) = Sum_{k=1..n} (-1)^(n-k)*k^(k-2)*n*(n-2)!*binomial(n-1,k-1)*(2*k*n - n - k^2)/k! for n > 1.
%F A331578 E.g.f.: -x - LambertW(-x/(1+x)) - (x/2)*LambertW(-x/(1+x))^2.
%F A331578 (End)
%e A331578 Non-isomorphic representatives of the a(7) = 847 trees (in the format root[branches]) are:
%e A331578   1[2,3,4[5,6,7]]
%e A331578   1[2,3,4,5[6,7]]
%e A331578   1[2,3,4,5,6,7]
%t A331578 lrt[set_]:=If[Length[set]==0,{},Join@@Table[Apply[root,#]&/@Join@@Table[Tuples[lrt/@stn],{stn,sps[DeleteCases[set,root]]}],{root,set}]];
%t A331578 Table[Length[Select[lrt[Range[n]],Length[#]>2&&FreeQ[#,_[_]]&]],{n,6}]
%o A331578 (PARI) a(n) = {if(n<=1, 0, sum(k=1, n, (-1)^(n-k)*k^(k-2)*n*(n-2)!*binomial(n-1,k-1)*(2*k*n - n - k^2)/k!))} \\ _Andrew Howroyd_, Dec 09 2020
%o A331578 (PARI) seq(n)={my(w=lambertw(-x/(1+x) + O(x*x^n))); Vec(serlaplace(-x - w - (x/2)*w^2), -n)} \\ _Andrew Howroyd_, Dec 09 2020
%Y A331578 The non-series-reduced version is A331577.
%Y A331578 The unlabeled version is A331488.
%Y A331578 Lone-child-avoiding rooted trees are counted by A001678.
%Y A331578 Topologically series-reduced rooted trees are counted by A001679.
%Y A331578 Labeled topologically series-reduced rooted trees are counted by A060313.
%Y A331578 Labeled lone-child-avoiding rooted trees are counted by A060356.
%Y A331578 Matula-Goebel numbers of lone-child-avoiding rooted trees are A291636.
%Y A331578 Matula-Goebel numbers of series-reduced rooted trees are A331489.
%Y A331578 Cf. A000014, A000169, A000669, A005512, A108919, A206429, A331233, A331490.
%K A331578 nonn
%O A331578 1,4
%A A331578 _Gus Wiseman_, Jan 21 2020
%E A331578 Terms a(9) and beyond from _Andrew Howroyd_, Dec 09 2020