A330467 - OEIS

%I #12 Dec 29 2020 16:38:54

%S 1,1,4,18,154,1614,23733,396190,8066984,183930948,4811382339,

%T 138718632336,4451963556127,155416836338920,5920554613563841,

%U 242873491536944706,10725017764009207613,505671090907469848248,25415190929321149684700,1354279188424092012064226

%N Number of series-reduced rooted trees whose leaves are multisets whose multiset union is a strongly normal multiset of size n.

%C A multiset is strongly normal if it covers an initial interval of positive integers with weakly decreasing multiplicities.

%C Also the number of different colorings of phylogenetic trees with n labels using strongly normal multisets of colors. A phylogenetic tree is a series-reduced rooted tree whose leaves are (usually disjoint) sets.

%e The a(3) = 18 trees:

%e   {1,1,1}          {1,1,2}          {1,2,3}

%e   {{1},{1,1}}      {{1},{1,2}}      {{1},{2,3}}

%e   {{1},{1},{1}}    {{2},{1,1}}      {{2},{1,3}}

%e   {{1},{{1},{1}}}  {{1},{1},{2}}    {{3},{1,2}}

%e                    {{1},{{1},{2}}}  {{1},{2},{3}}

%e                    {{2},{{1},{1}}}  {{1},{{2},{3}}}

%e                                     {{2},{{1},{3}}}

%e                                     {{3},{{1},{2}}}

%t strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];

%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,strnorm[n]}],{n,0,5}]

%o (PARI) \\ See links in A339645 for combinatorial species functions.

%o cycleIndexSeries(n)={my(v=vector(n), p=sExp(x*sv(1) + O(x*x^n))); v[1]=sv(1); for(n=2, #v, v[n] = polcoef( sExp(x*Ser(v[1..n])), n ) + polcoef(p, n)); 1 + x*Ser(v)}

%o StronglyNormalLabelingsSeq(cycleIndexSeries(15)) \\ _Andrew Howroyd_, Dec 28 2020

%Y The singleton-reduced version is A316652.

%Y The unlabeled version is A330465.

%Y Not requiring weakly decreasing multiplicities gives A330469.

%Y The case where the leaves are sets is A330625.

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

%K nonn

%O 0,3

%A _Gus Wiseman_, Dec 22 2019

%E Terms a(10) and beyond from _Andrew Howroyd_, Dec 28 2020