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

1, 1, 2, 3, 6, 13, 30, 72, 180, 458, 1194, 3160, 8459, 22881, 62417, 171526, 474405, 1319395, 3687711, 10352696, 29178988

Offset

1,3

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. It is an identity tree if no branch appears multiple times under the same root.

Links

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

Example

The a(6) = 13 trees:
6,
(15),
(1(14)),
(1(1(13))),
(1(1(1(12)))),
(1(23)), (2(13)), (3(12)), (123),
(1(2(12))), (2(1(12))), (12(12)),
(24).
Example of non-stable trees are ((12)(123)) and ((12)(12(12))).

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]], And[UnsameQ@@#, stableQ[#]]&], {ptn, Rest[IntegerPartitions[n]]}], {n}];
Table[Length[nms[n]], {n, 10}]

Crossrefs

Cf. A000081, A000669, A001678, A004111, A141268, A292504, A300660, A316467, A316474, A316653, A316654, A316656.

Sequence in context: A174191 A052937 A005554 * A300660 A077212 A076836

Adjacent sequences: A316763 A316764 A316765 * A316767 A316768 A316769

Keyword

nonn,more

Author

Gus Wiseman, Jul 12 2018

Extensions

a(18)-a(21) from Robert Price, Sep 14 2018

Status

approved