login
Number of series-reduced locally stable rooted trees with n unlabeled leaves.
0

%I #7 Sep 14 2018 15:56:54

%S 1,1,2,5,11,29,74,205,578,1683,4978,15000,45672,140600,436421,1364876,

%T 4295403,13594685,43238514

%N Number of series-reduced locally stable rooted trees with n unlabeled leaves.

%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 proper submultiset of any other branch of the same root.

%e The a(5) = 11 trees:

%e (o(o(o(oo))))

%e (o(o(ooo)))

%e (o((oo)(oo)))

%e (o(oo(oo)))

%e (o(oooo))

%e ((oo)(o(oo)))

%e (oo(o(oo)))

%e (oo(ooo))

%e (o(oo)(oo))

%e (ooo(oo))

%e (ooooo)

%e Missing from this list but counted by A000669 is ((oo)(ooo)).

%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]=If[n==1,{{1}},Join@@Table[Select[Union[Sort/@Tuples[nms/@ptn]],stableQ],{ptn,Rest[IntegerPartitions[n]]}]];

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

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

%K nonn,more

%O 1,3

%A _Gus Wiseman_, Jul 12 2018

%E a(17)-a(19) from _Robert Price_, Sep 14 2018