login
Number of series-reduced rooted trees whose leaves are multisets with a total of n elements covering an initial interval of positive integers.
10

%I #12 Feb 28 2020 12:56:23

%S 1,1,4,24,250,3744,73408,1768088,50468854,1664844040,62304622320,

%T 2607765903568,120696071556230,6120415124163512,337440974546042416,

%U 20096905939846645064,1285779618228281270718,87947859243850506008984,6404472598196204610148232

%N Number of series-reduced rooted trees whose leaves are multisets with a total of n elements covering an initial interval of positive integers.

%C Also the number of different colorings of phylogenetic trees with n labels using a multiset of colors covering an initial interval of positive integers. A phylogenetic tree is a series-reduced rooted tree whose leaves are (usually disjoint) sets.

%H Andrew Howroyd, <a href="/A330469/b330469.txt">Table of n, a(n) for n = 0..200</a>

%e The a(3) = 24 trees:

%e (123) (122) (112) (111)

%e ((1)(23)) ((1)(22)) ((1)(12)) ((1)(11))

%e ((2)(13)) ((2)(12)) ((2)(11)) ((1)(1)(1))

%e ((3)(12)) ((1)(2)(2)) ((1)(1)(2)) ((1)((1)(1)))

%e ((1)(2)(3)) ((1)((2)(2))) ((1)((1)(2)))

%e ((1)((2)(3))) ((2)((1)(2))) ((2)((1)(1)))

%e ((2)((1)(3)))

%e ((3)((1)(2)))

%t allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];

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

%t mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];

%t multing[t_,n_]:=Array[(t+#-1)/#&,n,1,Times];

%t amemo[m_]:=amemo[m]=1+Sum[Product[multing[amemo[s[[1]]],Length[s]],{s,Split[c]}],{c,Select[mps[m],Length[#]>1&]}];

%t Table[Sum[amemo[m],{m,allnorm[n]}],{n,0,5}]

%o (PARI)

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

%o R(n, k)={my(v=[]); for(n=1, n, v=concat(v, EulerT(concat(v, [binomial(n+k-1, k-1)]))[n])); v}

%o seq(n)={concat([1], sum(k=1, n, R(n,k)*sum(r=k, n, binomial(r,k)*(-1)^(r-k))))} \\ _Andrew Howroyd_, Dec 29 2019

%Y The singleton-reduced version is A316651.

%Y The unlabeled version is A330465.

%Y The strongly normal case is A330467.

%Y The case when leaves are sets is A330764.

%Y Row sums of A330762.

%Y Cf. A000311, A000669, A004114, A005121, A005804, A141268, A292504, A292505, A316652, A318812, A318849, A319312, A330625.

%K nonn

%O 0,3

%A _Gus Wiseman_, Dec 22 2019

%E Terms a(9) and beyond from _Andrew Howroyd_, Dec 29 2019