|
%I #12 Nov 16 2021 07:10:17
%S 1,1,1,3,5,11,24,52,119,272,635,1499,3577,8614,20903,51076,125565,
%T 310302,770536,1921440,4809851,12081986,30445041,76938794,194950040,
%U 495174037,1260576786,3215772264,8219437433,21046602265,53982543827,138678541693,356785641107
%N Number of singleton-reduced unlabeled rooted trees with n nodes.
%C A rooted tree is singleton-reduced if no non-leaf node has all singleton branches, where a rooted tree is a singleton if its root has degree 1.
%H Andrew Howroyd, <a href="/A330951/b330951.txt">Table of n, a(n) for n = 1..1000</a>
%F G.f.: A(x) satisfies A(x) = x + x*exp(Sum_{k>=1} A(x^k)/k) - x*exp(Sum_{k>=1} x^k*A(x^k)/(1 + x^k)/k). - _Andrew Howroyd_, Dec 10 2020
%F a(n) ~ c * d^n / n^(3/2), where d = 2.69474016697407303512228736537683134987637576... and c = 0.41800971384719166056172258174139385922545... - _Vaclav Kotesovec_, Nov 16 2021
%e The a(1) = 1 through a(6) = 11 trees:
%e o (o) (oo) (ooo) (oooo) (ooooo)
%e ((oo)) ((ooo)) ((oooo))
%e (o(o)) (o(oo)) (o(ooo))
%e (oo(o)) (oo(oo))
%e ((o(o))) (ooo(o))
%e ((o)(oo))
%e ((o(oo)))
%e ((oo(o)))
%e (o((oo)))
%e (o(o)(o))
%e (o(o(o)))
%t urt[n_]:=Join@@Table[Union[Sort/@Tuples[urt/@ptn]],{ptn,IntegerPartitions[n-1]}];
%t Table[Length[Select[urt[n],FreeQ[#,q:{__List}/;Times@@Length/@q==1]&]],{n,10}]
%o (PARI) EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
%o seq(n)={my(v=vector(n)); v[1]=1; for(n=1, #v-1, v[n+1] = EulerT(v[1..n])[n] - EulerT(Vec(x^2*Ser(v[1..n-1])/(1+x), -n))[n]); v} \\ _Andrew Howroyd_, Dec 10 2020
%Y The Matula-Goebel numbers of these trees are given by A330943.
%Y The series-reduced case is A001678.
%Y Unlabeled rooted trees are counted by A000081.
%Y Singleton-reduced phylogenetic trees are A000311.
%Y Cf. A000669, A003238, A004111, A324694.
%K nonn
%O 1,4
%A _Gus Wiseman_, Jan 15 2020
%E Terms a(19) and beyond from _Andrew Howroyd_, Dec 10 2020
| 