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

Author

Gus Wiseman, Jul 12 2018

Keywords

• nonn
• more

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.

Examples

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

Crossrefs

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

Programs

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}]

Extensions

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