A320289 Number of phylogenetic trees with n labels and no singleton leaves.

0, 1, 1, 4, 11, 86, 477, 4810, 40679, 496522, 5662933, 81759910, 1169640551, 19622623190, 336215135973, 6455705990674, 128445712218263, 2785761076726066, 62980942321570981, 1525318051255683598, 38566041706375722071, 1032726237783455193662

Offset

1,4

Links

Andrew Howroyd, Table of n, a(n) for n = 1..200

Example

The a(2) = 1 through a(5) = 11 phylogenetic trees:
  (12)  (123)  (1234)      (12345)
               ((12)(34))  ((12)(345))
               ((13)(24))  ((13)(245))
               ((14)(23))  ((14)(235))
                           ((15)(234))
                           ((23)(145))
                           ((24)(135))
                           ((25)(134))
                           ((34)(125))
                           ((35)(124))
                           ((45)(123))

Mathematica

numSetPtnsOfType[ptn_]:=Total[ptn]!/Times@@Factorial/@ptn/Times@@Factorial/@Length/@Split[ptn];
rotf[n_]:=rotf[n]=If[n==1, 0, 1+Sum[numSetPtnsOfType[p]*Times@@rotf/@p, {p, Select[IntegerPartitions[n], Length[#]>1&]}]];
Array[rotf, 20]

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=2, 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

Cf. A000311, A000669, A002865, A005804, A141268, A300660, A304966, A304967, A319312, A320294, A320295.

Sequence in context: A181275 A000850 A004796 * A298858 A181267 A280036

Adjacent sequences: A320286 A320287 A320288 * A320290 A320291 A320292

Keyword

nonn

Author

Gus Wiseman, Oct 09 2018

Status

approved