|
|
A005804
|
|
Number of phylogenetic rooted trees with n labels.
(Formerly M1890)
|
|
63
|
|
|
1, 2, 8, 58, 612, 8374, 140408, 2785906, 63830764, 1658336270, 48169385024, 1546832023114, 54413083601268, 2080827594898342, 85948745163598088, 3813417859420469410, 180876816831806597500, 9133309115320844870078, 489156459621633161274704, 27696066472039561313329018
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
These are series-reduced rooted trees where each leaf is a nonempty subset of the set of n labels.
|
|
REFERENCES
|
Foulds, L. R.; Robinson, R. W. Enumeration of phylogenetic trees without points of degree two. Ars Combin. 17 (1984), A, 169-183. Math. Rev. 85f:05045
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
FORMULA
|
Stirling transform of [ 1, 1, 4, 26, 236, ... ] = A000311 [ Foulds and Robinson ].
E.g.f.: -LambertW(-(1/2)*exp((1/2)*exp(z) - 1)) + (1/2)*exp(z) - 1. - Thomas Wieder, Jun 20 2008
a(n) ~ sqrt(log(2))*(log(2)+log(log(2)))^(1/2-n)*n^(n-1)/exp(n). - Vaclav Kotesovec, Aug 07 2013
E.g.f. f(x) satisfies 2*f(x) - exp(f(x)) = exp(x) - 2. - Gus Wiseman, Jul 31 2018
|
|
EXAMPLE
|
a(3)=8 because we have:
Set(Set(Z[3]),Set(Z[1]),Set(Z[2])),
Set(Z[3],Z[2],Z[1]),
Set(Set(Z[3],Z[1]),Set(Z[2])),
Set(Set(Set(Z[3]),Set(Z[2])),Set(Z[1])),
Set(Set(Set(Z[3]),Set(Z[1])),Set(Z[2])),
Set(Set(Z[3]),Set(Set(Z[1]),Set(Z[2]))),
Set(Set(Z[3]),Set(Z[2],Z[1])),
Set(Set(Z[3],Z[2]),Set(Z[1])).
The 8 series-reduced rooted trees whose leaves are a set partition of {1,2,3}:
{1,2,3}
({1}{2,3})
({1}({2}{3}))
({2}{1,3})
({2}({1}{3}))
({3}{1,2})
({3}({1}{2}))
({1}{2}{3})
(End)
|
|
MAPLE
|
ser := series(-LambertW(-1/2*exp(1/2*exp(z)-1)) + 1/2*exp(z)-1, z=0, 10);
seq(n!*coeff(ser, z, n), n = 1..9);
# Alternative:
with(combstruct):
A005804 := [H, {H=Union(Set(Z, card>=1), Set(H, card>=2))}, labelled];
seq(count(A005804, size=j), j=1..20);
# (End)
|
|
MATHEMATICA
|
numSetPtnsOfType[ptn_]:=Total[ptn]!/Times@@Factorial/@ptn/Times@@Factorial/@Length/@Split[ptn];
a[n_]:=a[n]=If[n==1, 1, 1+Sum[numSetPtnsOfType[ptn]*Times@@a/@ptn, {ptn, Rest[IntegerPartitions[n]]}]];
|
|
PROG
|
(PARI) EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
b(n, k)={my(v=vector(n)); for(n=1, n, v[n]=binomial(n+k-1, n) + EulerT(v[1..n])[n]); v}
seq(n)={my(M=Mat(vectorv(n, k, b(n, k)))); vector(n, k, sum(i=1, k, binomial(k, i)*(-1)^(k-i)*M[i, k]))} \\ Andrew Howroyd, Oct 26 2018
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|