OFFSET
1,4
COMMENTS
A rooted tree is series-reduced if no vertex (including the root) has degree 2.
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.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..200
FORMULA
From Andrew Howroyd, Dec 09 2020: (Start)
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.
E.g.f.: -x - LambertW(-x/(1+x)) - (x/2)*LambertW(-x/(1+x))^2.
(End)
EXAMPLE
Non-isomorphic representatives of the a(7) = 847 trees (in the format root[branches]) are:
1[2,3,4[5,6,7]]
1[2,3,4,5[6,7]]
1[2,3,4,5,6,7]
MATHEMATICA
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]], Length[#]>2&&FreeQ[#, _[_]]&]], {n, 6}]
PROG
(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
(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
CROSSREFS
The non-series-reduced version is A331577.
The unlabeled version is A331488.
Lone-child-avoiding rooted trees are counted by A001678.
Topologically series-reduced rooted trees are counted by A001679.
Labeled topologically series-reduced rooted trees are counted by A060313.
Labeled lone-child-avoiding rooted trees are counted by A060356.
Matula-Goebel numbers of lone-child-avoiding rooted trees are A291636.
Matula-Goebel numbers of series-reduced rooted trees are A331489.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jan 21 2020
EXTENSIONS
Terms a(9) and beyond from Andrew Howroyd, Dec 09 2020
STATUS
approved