A319285 - OEIS

%I #4 Sep 17 2018 08:34:34

%S 1,2,9,69,619,7739,109855,1898230

%N Number of series-reduced locally stable rooted trees whose leaves span an initial interval of positive integers with multiplicities an integer partition of n.

%C A rooted tree is series-reduced if every non-leaf node has at least two branches. It is locally stable if no branch is a submultiset of any other branch of the same root.

%e The a(3) = 9 trees:

%e   (1(11))

%e    (111)

%e   (1(12))

%e   (2(11))

%e    (112)

%e   (1(23))

%e   (2(13))

%e   (3(12))

%e    (123)

%e Examples of rooted trees that are not locally stable are ((11)(111)), ((11)(112)), ((12)(112)), ((12)(123)).

%t submultisetQ[M_,N_]:=Or[Length[M]==0,MatchQ[{Sort[List@@M],Sort[List@@N]},{{x_,Z___},{___,x_,W___}}/;submultisetQ[{Z},{W}]]];

%t stableQ[u_]:=Apply[And,Outer[#1==#2||!submultisetQ[#1,#2]&&!submultisetQ[#2,#1]&,u,u,1],{0,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 gro[m_]:=gro[m]=If[Length[m]==1,{m},Select[Union[Sort/@Join@@(Tuples[gro/@#]&/@Select[mps[m],Length[#]>1&])],stableQ]];

%t Table[Sum[Length[gro[m]],{m,Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n]}],{n,5}]

%Y Cf. A000081, A316466, A316468, A316469, A316473, A316475.

%K nonn,more

%O 1,2

%A _Gus Wiseman_, Sep 16 2018