|
|
A330951
|
|
Number of singleton-reduced unlabeled rooted trees with n nodes.
|
|
9
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
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.
|
|
LINKS
|
|
|
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
|
|
EXAMPLE
|
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)))
|
|
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}]
|
|
PROG
|
(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
|
|
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.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|