login
Number of series-reduced balanced rooted trees with n labeled leaves.
8

%I #21 Nov 18 2021 03:58:28

%S 1,1,1,4,11,41,162,1030,7205,55522,442443,3810852,35272030,351697516,

%T 3735838550,42719792640,529195988635,7128835815387,103651381499810,

%U 1610812109555323,26489497655582729,457497408108551450,8248899117402701046,154624472715479106919

%N Number of series-reduced balanced rooted trees with n labeled leaves.

%C 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.

%H Andrew Howroyd, <a href="/A320155/b320155.txt">Table of n, a(n) for n = 1..200</a>

%F E.g.f. A(x) satisfies A(x) = x + A(exp(x)-x-1). - _Ira M. Gessel_, Nov 17 2021

%e The a(1) = 1 through a(5) = 11 rooted trees:

%e 1 (12) (123) (1234) (12345)

%e ((12)(34)) ((12)(345))

%e ((13)(24)) ((13)(245))

%e ((14)(23)) ((14)(235))

%e ((15)(234))

%e ((23)(145))

%e ((24)(135))

%e ((25)(134))

%e ((34)(125))

%e ((35)(124))

%e ((45)(123))

%t sps[{}]:={{}};sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];

%t phy2[labs_]:=If[Length[labs]==1,labs,Union@@Table[Sort/@Tuples[phy2/@ptn],{ptn,Select[sps[Sort[labs]],Length[#1]>1&]}]];

%t Table[Length[Select[phy2[Range[n]],SameQ@@Length/@Position[#,_Integer]&]],{n,7}]

%o (PARI) EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}

%o b(n,k)={my(u=vector(n), v=vector(n)); u[1]=k; while(u, v+=u; u=EulerT(u)-u); v}

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

%Y Cf. A000081, A000311, A000669, A001678, A005804, A048816, A079500, A119262, A120803, A141268, A244925, A319312.

%Y Cf. A320154, A320160, A316624, A320169, A320173, A320179.

%K nonn

%O 1,4

%A _Gus Wiseman_, Oct 06 2018

%E Terms a(10) and beyond from _Andrew Howroyd_, Oct 26 2018