A330951 Number of singleton-reduced unlabeled rooted trees with n nodes.

1, 1, 1, 3, 5, 11, 24, 52, 119, 272, 635, 1499, 3577, 8614, 20903, 51076, 125565, 310302, 770536, 1921440, 4809851, 12081986, 30445041, 76938794, 194950040, 495174037, 1260576786, 3215772264, 8219437433, 21046602265, 53982543827, 138678541693, 356785641107

Offset: 1

Author

Gus Wiseman, Jan 15 2020

Keywords

• nonn

Comments

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.

Examples

			The a(1) = 1 through a(6) = 11 trees:
  o  (o)  (oo)  (ooo)   (oooo)    (ooooo)
                ((oo))  ((ooo))   ((oooo))
                (o(o))  (o(oo))   (o(ooo))
                        (oo(o))   (oo(oo))
                        ((o(o)))  (ooo(o))
                                  ((o)(oo))
                                  ((o(oo)))
                                  ((oo(o)))
                                  (o((oo)))
                                  (o(o)(o))
                                  (o(o(o)))
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1000

Crossrefs

The Matula-Goebel numbers of these trees are given by A330943.

The series-reduced case is A001678.

Unlabeled rooted trees are counted by A000081.

Singleton-reduced phylogenetic trees are A000311.

Cf. A000669, A003238, A004111, A324694.

Programs

Mathematica

urt[n_]:=Join@@Table[Union[Sort/@Tuples[urt/@ptn]],{ptn,IntegerPartitions[n-1]}];
Table[Length[Select[urt[n],FreeQ[#,q:{__List}/;Times@@Length/@q==1]&]],{n,10}]

PARI

EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
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

Formula

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

a(n) ~ c * d^n / n^(3/2), where d = 2.69474016697407303512228736537683134987637576... and c = 0.41800971384719166056172258174139385922545... - Vaclav Kotesovec, Nov 16 2021

Extensions

Terms a(19) and beyond from Andrew Howroyd, Dec 10 2020