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

%I #10 Sep 17 2018 03:17:21

%S 1,2,4,11,29,91,284,950,3235,11336,40370,146095,534774,1977891,

%T 7377235,27719883

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

%C 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.

%e The a(5) = 29 trees:

%e 5,

%e (14),

%e (23),

%e (1(13)), (3(11)), (113),

%e (1(22)), (2(12)), (122),

%e (1(1(12))), (1(2(11))), (1(112)), (2(1(11))), (2(111)), ((11)(12)), (11(12)), (12(11)), (1112),

%e (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).

%e Missing from this list but counted by A141268 is ((11)(111)).

%t submultisetQ[M_,N_]:=Or[Length[M]==0,MatchQ[{Sort[List@@M],Sort[List@@N]},{{x_,Z___},{___,x_,W___}}/;submultisetQ[{Z},{W}]]];

%t stableQ[u_]:=Apply[And,Outer[#1==#2||!submultisetQ[#1,#2]&&!submultisetQ[#2,#1]&,u,u,1],{0,1}];

%t nms[n_]:=nms[n]=Prepend[Join@@Table[Select[Union[Sort/@Tuples[nms/@ptn]],stableQ],{ptn,Rest[IntegerPartitions[n]]}],{n}];

%t Table[Length[nms[n]],{n,10}]

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

%K nonn,more

%O 1,2

%A _Gus Wiseman_, Jul 12 2018

%E a(15)-a(16) from _Robert Price_, Sep 16 2018