A316696 Number of lone-child-avoiding locally disjoint rooted trees whose leaves form an integer partition of n.

1, 2, 4, 11, 27, 80, 218, 654, 1923, 5924, 18310, 58176, 186341, 606814, 1993420, 6618160, 22134640

Offset

1,2

Comments

A rooted tree is lone-child-avoiding 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..17.

Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.

Example

The a(4) = 11 rooted trees:
  4,
  (13),
  (22),
  (1(12)), (2(11)), (112),
  (1(1(11))), (1(111)), ((11)(11)), (11(11)), (1111).

Mathematica

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

Crossrefs

Matula-Goebel numbers of locally disjoint rooted trees are A316495.

The case where all leaves are 1's is A316697.

Lone-child-avoiding locally disjoint rooted trees are A331680.

Cf. A000669, A001678, A141268, A316473, A316652, A331678, A331686, A331687, A331871, A331872, A331874.

Sequence in context: A309886 A123441 A086441 * A319616 A148130 A350030

Adjacent sequences: A316693 A316694 A316695 * A316697 A316698 A316699

Keyword

nonn,more

Author

Gus Wiseman, Jul 10 2018

Extensions

a(16)-a(17) from Robert Price, Sep 16 2018

Terminology corrected by Gus Wiseman, Feb 06 2020

Status

approved