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

1, 1, 2, 5, 11, 29, 74, 205, 578, 1683, 4978, 15000, 45672, 140600, 436421, 1364876, 4295403, 13594685, 43238514

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

Examples

			The a(5) = 11 trees:
  (o(o(o(oo))))
  (o(o(ooo)))
  (o((oo)(oo)))
  (o(oo(oo)))
  (o(oooo))
  ((oo)(o(oo)))
  (oo(o(oo)))
  (oo(ooo))
  (o(oo)(oo))
  (ooo(oo))
  (ooooo)
Missing from this list but counted by A000669 is ((oo)(ooo)).
		

Crossrefs

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

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

Extensions

a(17)-a(19) from Robert Price, Sep 14 2018