|
|
A005640
|
|
Number of phylogenetic trees with n labels.
(Formerly M1896)
|
|
8
|
|
|
1, 1, 2, 8, 64, 832, 15104, 352256, 10037248, 337936384, 13126565888, 577818263552, 28425821618176, 1545553369366528, 92034646352592896, 5956917762776367104, 416397789920380321792, 31262503202358260924416
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Each node of the tree is a subset of the labeled set {1,...,n}. If the subset node is empty, it must have degree at least 3.
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.26.
|
|
LINKS
|
L. R. Foulds and R. W. Robinson, Determining the asymptotic number of phylogenetic trees, pp. 110-126 of Combinatorial Mathematics VII (Newcastle, August 1979), ed. R. W. Robinson, G. W. Southern and W. D. Wallis. Lecture Notes in Math., 829 (1980), 110-126. (Annotated scanned copy)
|
|
FORMULA
|
E.g.f.: 1+B(x)-B(x)^2 where B(x) is e.g.f. of A005172.
|
|
MATHEMATICA
|
a[n_ /; n > 2] := 2^(n-1)*(n-2)!*Sum[ Binomial[n+k-2, n-2]*Sum[ (-1)^j*Binomial[k, j]*Sum[ ((-1)^l*2^(j-l)*Binomial[j, l]*(j-l)!*StirlingS1[n+j-l-2, j-l])/(n+j-l-2)!, {l, 0, j}], {j, 1, k}], {k, 1, n-2}]; a[0] = a[1] = 1; a[2] = 2; Table[a[n], {n, 0, 17}] (* Jean-François Alcover, Apr 10 2012, after Vladimir Kruchinin *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|