|
%I M1896 #37 Oct 04 2017 00:34:52
%S 1,1,2,8,64,832,15104,352256,10037248,337936384,13126565888,
%T 577818263552,28425821618176,1545553369366528,92034646352592896,
%U 5956917762776367104,416397789920380321792,31262503202358260924416
%N Number of phylogenetic trees with n labels.
%C 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.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.26.
%H Vincenzo Librandi, <a href="/A005640/b005640.txt">Table of n, a(n) for n = 0..100</a>
%H L. R. Foulds and R. W. Robinson, <a href="/A005172/a005172_1.pdf">Determining the asymptotic number of phylogenetic trees</a>, 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)
%H J. P. Hayes, <a href="http://dx.doi.org/10.1145/321978.321988">Enumeration of fanout-free Boolean functions</a>, J. ACM, 23 (1976), 700-709.
%H K. L. Kodandapani and S. C. Seth, <a href="http://dx.doi.org/10.1109/TC.1978.1675103">On combinational networks with restricted fan-out</a>, IEEE Trans. Computers, 27 (1978), 309-318. (<a href="/A005736/a005736.pdf">Annotated scanned copy</a>)
%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F STIRLING transform of A005263.
%F E.g.f.: 1+B(x)-B(x)^2 where B(x) is e.g.f. of A005172.
%F For n >= 2, a(n) = 2^n*A006351(n) = 2^(n+1)*A000311(n).
%t 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_ *)
%Y Cf. A000311, A005172, A005263, A006351.
%K nonn,nice,easy
%O 0,3
%A _N. J. A. Sloane_
%E More terms, formula and comment from _Christian G. Bower_, Nov 15 1999
|
