A005805 - OEIS

%I M1519 #42 Nov 16 2021 05:09:51

%S 1,2,5,18,107,1008,13113,214238,4182487,94747196,2440784645,

%T 70431957258,2249856084803,78802876705608,3002702793753489,

%U 123649410977736950,5471808106109912815,258948617502187143188,13049542794706527317597,697673361673877090147490

%N Number of phylogenetic trees with n labels.

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

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

%D 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

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Alois P. Heinz, <a href="/A005805/b005805.txt">Table of n, a(n) for n = 1..381</a> (first 100 terms from Vincenzo Librandi)

%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 From _Vaclav Kotesovec_, Nov 16 2021: (Start)

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

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

%F (End)

%p 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:

%p a:= stirtr(n->`if`(n<2,1, b(n-1))):

%p seq(a(n), n=1..20);  # _Alois P. Heinz_, Sep 15 2008

%t 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 *)

%Y Cf. A000311, A005804.

%K nonn,easy

%O 1,2

%A _N. J. A. Sloane_

%E More terms from _Christian G. Bower_, Dec 15 1999