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,3

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.

Links

Table of n, a(n) for n=1..22.

Example

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

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

Crossrefs

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

Sequence in context: A049937 A026754 A291247 * A032170 A084081 A106376

Adjacent sequences: A316694 A316695 A316696 * A316698 A316699 A316700

Keyword

nonn,more

Author

Gus Wiseman, Jul 10 2018

Extensions

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

Status

approved