login
Number of series/singleton-reduced rooted trees on strongly normal multisets of size n whose leaves are sets (not necessarily disjoint).
8

%I #8 Feb 28 2020 13:01:31

%S 1,1,1,5,42,423,5458,80926

%N Number of series/singleton-reduced rooted trees on strongly normal multisets of size n whose leaves are sets (not necessarily disjoint).

%C A series/singleton-reduced rooted tree on a multiset m is either the multiset m itself or a sequence of series/singleton-reduced rooted trees, one on each part of a multiset partition of m that is neither minimal (all singletons) nor maximal (only one part).

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

%e The a(4) = 42 trees:

%e {{1}{1}{12}} {{12}{12}} {{1}{123}} {1234}

%e {{1}{{1}{12}}} {{1}{2}{12}} {{12}{13}} {{1}{234}}

%e {{1}{{2}{12}}} {{1}{1}{23}} {{12}{34}}

%e {{2}{{1}{12}}} {{1}{2}{13}} {{13}{24}}

%e {{1}{3}{12}} {{14}{23}}

%e {{1}{{1}{23}}} {{2}{134}}

%e {{1}{{2}{13}}} {{3}{124}}

%e {{1}{{3}{12}}} {{4}{123}}

%e {{2}{{1}{13}}} {{1}{2}{34}}

%e {{3}{{1}{12}}} {{1}{3}{24}}

%e {{1}{4}{23}}

%e {{2}{3}{14}}

%e {{2}{4}{13}}

%e {{3}{4}{12}}

%e {{1}{{2}{34}}}

%e {{1}{{3}{24}}}

%e {{1}{{4}{23}}}

%e {{2}{{1}{34}}}

%e {{2}{{3}{14}}}

%e {{2}{{4}{13}}}

%e {{3}{{1}{24}}}

%e {{3}{{2}{14}}}

%e {{3}{{4}{12}}}

%e {{4}{{1}{23}}}

%e {{4}{{2}{13}}}

%e {{4}{{3}{12}}}

%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 strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];

%t ssrtrees[m_]:=Prepend[Join@@Table[Tuples[ssrtrees/@p],{p,Select[mps[m],Length[m]>Length[#1]>1&]}],m];

%t Table[Sum[Length[Select[ssrtrees[s],FreeQ[#,{___,x_Integer,x_Integer,___}]&]],{s,strnorm[n]}],{n,0,5}]

%Y The generalization where leaves are multisets is A330471.

%Y The non-singleton-reduced version is A330625.

%Y The unlabeled version is A330626.

%Y The case with all atoms distinct is A000311.

%Y Strongly normal multiset partitions are A035310.

%Y Cf. A000669, A004111, A004114, A005804, A196545, A281118, A330465, A330467, A330624, A330654, A330668.

%K nonn,more

%O 0,4

%A _Gus Wiseman_, Dec 26 2019