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

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

Offset

0,3

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

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.

Links

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

Example

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

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]]]];
allnorm[n_]:=If[n<=0, {{}}, Function[s, Array[Count[s, y_/; y<=#]+1&, n]]/@Subsets[Range[n-1]+1]];
ssrtrees[m_]:=Prepend[Join@@Table[Tuples[ssrtrees/@p], {p, Select[mps[m], Length[m]>Length[#1]>1&]}], m];
Table[Sum[Length[ssrtrees[s]], {s, allnorm[n]}], {n, 0, 5}]

Crossrefs

The orderless version is A316651.

The strongly normal case is A330471.

The unlabeled version is A330470.

The balanced version is A330655.

The case with all atoms distinct is A000311.

The case with all atoms equal is A196545.

Normal multiset partitions are A255906.

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

Sequence in context: A185190 A227460 A316651 * A091481 A053312 A091854

Adjacent sequences: A330651 A330652 A330653 * A330655 A330656 A330657

Keyword

nonn,more

Author

Gus Wiseman, Dec 26 2019

Status

approved