A316697 Number of series-reduced locally disjoint rooted trees with n unlabeled leaves.

1, 1, 2, 5, 10, 24, 49, 112, 241, 548, 1218, 2839, 6547, 15572, 37179, 90555, 222065, 552576, 1384820, 3506475, 8936121, 22941280

Offset: 1

Author

Gus Wiseman, Jul 10 2018

Keywords

• nonn
• more

Comments

A rooted tree is series-reduced if every non-leaf node has at least two branches. It is locally disjoint if no branch overlaps any other (unequal) branch of the same root.

Examples

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

Crossrefs

Cf. A000081, A000669, A001678, A141268, A316471, A316471, A316475, A316495.

Programs

Mathematica

disjointQ[u_]:=Apply[And,Outer[#1==#2||Intersection[#1,#2]=={}&,u,u,1],{0,1}];
nms[n_]:=nms[n]=If[n==1,{{1}},Join@@Table[Select[Union[Sort/@Tuples[nms/@ptn]],disjointQ],{ptn,Rest[IntegerPartitions[n]]}]];
Table[Length[nms[n]],{n,15}]

Extensions

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