A330625 Number of series-reduced rooted trees whose leaves are sets (not necessarily disjoint) with multiset union a strongly normal multiset of size n.

1, 1, 3, 14, 123, 1330, 19694

Offset: 0

Author

Gus Wiseman, Dec 25 2019

Keywords

• nonn
• more

Comments

A rooted tree is series-reduced if it has no unary branchings, so every non-leaf node covers at least two other nodes.

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

Examples

			The a(1) = 1 through a(3) = 14 trees:
  {1}  {1,2}      {1,2,3}
       {{1},{1}}  {{1},{1,2}}
       {{1},{2}}  {{1},{2,3}}
                  {{2},{1,3}}
                  {{3},{1,2}}
                  {{1},{1},{1}}
                  {{1},{1},{2}}
                  {{1},{2},{3}}
                  {{1},{{1},{1}}}
                  {{1},{{1},{2}}}
                  {{1},{{2},{3}}}
                  {{2},{{1},{1}}}
                  {{2},{{1},{3}}}
                  {{3},{{1},{2}}}
		

Crossrefs

The generalization where the leaves are multisets is A330467.

The singleton-reduced case is A330628.

The unlabeled version is A330624.

The case with all atoms distinct is A005804.

The case with all atoms equal is A196545.

The case where all leaves are singletons is A330471.

Cf. A000669, A004111, A141268, A300660, A316652, A330469, A330475, A330626, A330668, A330675.

Programs

Mathematica

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];
srtrees[m_]:=Prepend[Join@@Table[Tuples[srtrees/@p],{p,Select[mps[m],Length[#1]>1&]}],m];
Table[Sum[Length[Select[srtrees[s],FreeQ[#,{_,x_Integer,x_Integer,_}]&]],{s,strnorm[n]}],{n,0,5}]