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

1, 1, 1, 5, 42, 423, 5458, 80926

Offset

0,4

Comments

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).

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

Links

Table of n, a(n) for n=0..7.

Example

The a(4) = 42 trees:
  {{1}{1}{12}}    {{12}{12}}      {{1}{123}}      {1234}
  {{1}{{1}{12}}}  {{1}{2}{12}}    {{12}{13}}      {{1}{234}}
                  {{1}{{2}{12}}}  {{1}{1}{23}}    {{12}{34}}
                  {{2}{{1}{12}}}  {{1}{2}{13}}    {{13}{24}}
                                  {{1}{3}{12}}    {{14}{23}}
                                  {{1}{{1}{23}}}  {{2}{134}}
                                  {{1}{{2}{13}}}  {{3}{124}}
                                  {{1}{{3}{12}}}  {{4}{123}}
                                  {{2}{{1}{13}}}  {{1}{2}{34}}
                                  {{3}{{1}{12}}}  {{1}{3}{24}}
                                                  {{1}{4}{23}}
                                                  {{2}{3}{14}}
                                                  {{2}{4}{13}}
                                                  {{3}{4}{12}}
                                                  {{1}{{2}{34}}}
                                                  {{1}{{3}{24}}}
                                                  {{1}{{4}{23}}}
                                                  {{2}{{1}{34}}}
                                                  {{2}{{3}{14}}}
                                                  {{2}{{4}{13}}}
                                                  {{3}{{1}{24}}}
                                                  {{3}{{2}{14}}}
                                                  {{3}{{4}{12}}}
                                                  {{4}{{1}{23}}}
                                                  {{4}{{2}{13}}}
                                                  {{4}{{3}{12}}}

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];
ssrtrees[m_]:=Prepend[Join@@Table[Tuples[ssrtrees/@p], {p, Select[mps[m], Length[m]>Length[#1]>1&]}], m];
Table[Sum[Length[Select[ssrtrees[s], FreeQ[#, {___, x_Integer, x_Integer, ___}]&]], {s, strnorm[n]}], {n, 0, 5}]

Crossrefs

The generalization where leaves are multisets is A330471.

The non-singleton-reduced version is A330625.

The unlabeled version is A330626.

The case with all atoms distinct is A000311.

Strongly normal multiset partitions are A035310.

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

Sequence in context: A082145 A126765 A228793 * A327272 A024492 A217805

Adjacent sequences: A330625 A330626 A330627 * A330629 A330630 A330631

Keyword

nonn,more

Author

Gus Wiseman, Dec 26 2019

Status

approved