A320154 Number of series-reduced balanced rooted trees whose leaves form a set partition of {1,...,n}.

1, 2, 5, 18, 92, 588, 4328, 35920, 338437, 3654751, 45105744, 625582147, 9539374171, 157031052142, 2757275781918, 51293875591794, 1007329489077804, 20840741773898303, 453654220906310222, 10380640686263467204, 249559854371799622350, 6301679967177242849680

Offset: 1

Author

Gus Wiseman, Oct 06 2018

Keywords

• nonn

Comments

A rooted tree is series-reduced if every non-leaf node has at least two branches, and balanced if all leaves are the same distance from the root.

Also the number of balanced phylogenetic rooted trees on n distinct labels.

Examples

			The a(1) = 1 through a(4) = 18 rooted trees:
  (1)  (12)      (123)        (1234)
       ((1)(2))  ((1)(23))    ((1)(234))
                 ((2)(13))    ((12)(34))
                 ((3)(12))    ((13)(24))
                 ((1)(2)(3))  ((14)(23))
                              ((2)(134))
                              ((3)(124))
                              ((4)(123))
                              ((1)(2)(34))
                              ((1)(3)(24))
                              ((1)(4)(23))
                              ((2)(3)(14))
                              ((2)(4)(13))
                              ((3)(4)(12))
                              ((1)(2)(3)(4))
                              (((1)(2))((3)(4)))
                              (((1)(3))((2)(4)))
                              (((1)(4))((2)(3)))
		

Links

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

Crossrefs

Cf. A000081, A000311, A000669, A001678, A005804, A048816, A079500, A119262, A120803, A141268, A244925, A292504, A300660, A319312.

Cf. A320155, A320160, A316624, A320169, A320173, A320176, A320179.

Programs

Mathematica

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
gug[m_]:=Prepend[Join@@Table[Union[Sort/@Tuples[gug/@mtn]],{mtn,Select[sps[m],Length[#]>1&]}],m];
Table[Length[Select[gug[Range[n]],SameQ@@Length/@Position[#,_Integer]&]],{n,9}]

PARI

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
b(n,k)={my(u=vector(n), v=vector(n)); u[1]=k; u=EulerT(u); while(u, v+=u; u=EulerT(u)-u); 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

Extensions

Terms a(9) and beyond from Andrew Howroyd, Oct 26 2018