login
Number of series/singleton-reduced rooted trees on normal multisets of size n.
5

%I #10 Feb 28 2020 12:56:44

%S 1,1,2,12,112,1444,24099,492434,11913985

%N Number of series/singleton-reduced rooted trees on normal multisets of size n.

%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 normal if it covers an initial interval of positive integers.

%C First differs from A316651 at a(6) = 24099, A316651(6) = 24086. For example, ((1(12))(2(11))) and ((2(11))(1(12))) are considered identical for A316651 (series-reduced rooted trees), but {{{1},{1,2}},{{2},{1,1}}} and {{{2},{1,1}},{{1},{1,2}}} are different series/singleton-reduced rooted trees.

%e The a(0) = 1 through a(3) = 12 trees:

%e {} {1} {1,1} {1,1,1}

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

%e {1,2,2}

%e {1,2,3}

%e {{1},{1,1}}

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

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

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

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

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

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

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

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

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

%t Table[Sum[Length[ssrtrees[s]],{s,allnorm[n]}],{n,0,5}]

%Y The orderless version is A316651.

%Y The strongly normal case is A330471.

%Y The unlabeled version is A330470.

%Y The balanced version is A330655.

%Y The case with all atoms distinct is A000311.

%Y The case with all atoms equal is A196545.

%Y Normal multiset partitions are A255906.

%Y Cf. A000669, A004114, A005804, A281118, A316651, A330469, A330626, A330676.

%K nonn,more

%O 0,3

%A _Gus Wiseman_, Dec 26 2019