A005805 Number of phylogenetic trees with n labels.

1, 2, 5, 18, 107, 1008, 13113, 214238, 4182487, 94747196, 2440784645, 70431957258, 2249856084803, 78802876705608, 3002702793753489, 123649410977736950, 5471808106109912815, 258948617502187143188, 13049542794706527317597, 697673361673877090147490

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

Stirling transform of [ 1, 1, 1, 4, 26, 236, ... ] = A000311(n-1).

Series-reduced trees where each leaf is a nonempty subset of the set of n labels. [Christian G. Bower, Dec 15 1999]

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

• Alois P. Heinz, Table of n, a(n) for n = 1..381 (first 100 terms from Vincenzo Librandi)
• N. J. A. Sloane, Transforms
• Index entries for sequences related to trees

Crossrefs

Cf. A000311, A005804.

Programs

Maple

stirtr:= proc(p) proc(n) add(p(k) *Stirling2(n,k), k=0..n) end end: b:= proc(n) option remember; if n<=1 then n elif n=2 then 1 else (n+1) *b(n-1) +2*add(binomial(n-1, k) *b(k) *b(n-k), k=2..n-2) fi end:
a:= stirtr(n->`if`(n<2,1, b(n-1))):
seq(a(n), n=1..20);  # Alois P. Heinz, Sep 15 2008

Mathematica

max = 18; a311 = CoefficientList[ InverseSeries[ Series[ 1 + 2x - E^x, {x, 0, max}], x], x]*Range[0, max]!; b[1] = 1; b[k_] := a311[[k]]; a[n_] := Sum[ b[k]*StirlingS2[n, k], {k, 1, n}]; Table[ a[n], {n, 1, max}] (* Jean-François Alcover, Feb 22 2012 *)

Formula

From Vaclav Kotesovec, Nov 16 2021: (Start)

E.g.f.: exp(2*x)/4 - (1 + LambertW(-exp(exp(x)/2 - 1)/2))^2.

a(n) ~ 2 * log(2)^(3/2) * n^(n-2) / (exp(n) * (log(2) + log(log(2)))^(n - 3/2)).

(End)

Extensions

More terms from Christian G. Bower, Dec 15 1999