A316768 Number of series-reduced locally stable rooted trees whose leaves form an integer partition of n.

1, 2, 4, 11, 29, 91, 284, 950, 3235, 11336, 40370, 146095, 534774, 1977891, 7377235, 27719883

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

Example

The a(5) = 29 trees:
  5,
  (14),
  (23),
  (1(13)), (3(11)), (113),
  (1(22)), (2(12)), (122),
  (1(1(12))), (1(2(11))), (1(112)), (2(1(11))), (2(111)), ((11)(12)), (11(12)), (12(11)), (1112),
  (1(1(1(11)))), (1(1(111))), (1((11)(11))), (1(11(11))), (1(1111)), ((11)(1(11))), (11(1(11))), (11(111)), (1(11)(11)), (111(11)), (11111).
Missing from this list but counted by A141268 is ((11)(111)).

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}];
nms[n_]:=nms[n]=Prepend[Join@@Table[Select[Union[Sort/@Tuples[nms/@ptn]], stableQ], {ptn, Rest[IntegerPartitions[n]]}], {n}];
Table[Length[nms[n]], {n, 10}]

Crossrefs

Cf. A000081, A000669, A001678, A141268, A292504, A316468, A316475, A316651, A316652, A316655.

Sequence in context: A148144 A148145 A052869 * A052831 A339834 A148146

Adjacent sequences: A316765 A316766 A316767 * A316769 A316770 A316771

Keyword

nonn,more

Author

Gus Wiseman, Jul 12 2018

Extensions

a(15)-a(16) from Robert Price, Sep 16 2018

Status

approved