A319285 Number of series-reduced locally stable rooted trees whose leaves span an initial interval of positive integers with multiplicities an integer partition of n.

1, 2, 9, 69, 619, 7739, 109855, 1898230

Offset

1,2

Comments

A rooted tree is series-reduced if every non-leaf node has at least two branches. It is locally stable if no branch is a submultiset of any other branch of the same root.

Links

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

Example

The a(3) = 9 trees:
  (1(11))
   (111)
  (1(12))
  (2(11))
   (112)
  (1(23))
  (2(13))
  (3(12))
   (123)
Examples of rooted trees that are not locally stable are ((11)(111)), ((11)(112)), ((12)(112)), ((12)(123)).

Mathematica

submultisetQ[M_, N_]:=Or[Length[M]==0, MatchQ[{Sort[List@@M], Sort[List@@N]}, {{x_, Z___}, {___, x_, W___}}/; submultisetQ[{Z}, {W}]]];
stableQ[u_]:=Apply[And, Outer[#1==#2||!submultisetQ[#1, #2]&&!submultisetQ[#2, #1]&, u, u, 1], {0, 1}];
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]]]];
gro[m_]:=gro[m]=If[Length[m]==1, {m}, Select[Union[Sort/@Join@@(Tuples[gro/@#]&/@Select[mps[m], Length[#]>1&])], stableQ]];
Table[Sum[Length[gro[m]], {m, Flatten[MapIndexed[Table[#2, {#1}]&, #]]&/@IntegerPartitions[n]}], {n, 5}]

Crossrefs

Cf. A000081, A316466, A316468, A316469, A316473, A316475.

Sequence in context: A255537 A272663 A006849 * A316652 A330471 A121417

Adjacent sequences: A319282 A319283 A319284 * A319286 A319287 A319288

Keyword

nonn,more

Author

Gus Wiseman, Sep 16 2018

Status

approved