A331679 Number of lone-child-avoiding locally disjoint rooted trees whose leaves are positive integers summing to n, with no two distinct leaves directly under the same vertex.

1, 2, 3, 8, 16, 48, 116, 341, 928, 2753, 7996, 24254, 73325, 226471, 702122

Offset

1,2

Comments

A tree is locally disjoint if no child of any vertex has branches overlapping the branches of any other unequal child of the same vertex. It is lone-child-avoiding if there are no unary branchings.

Links

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

David Callan, A sign-reversing involution to count labeled lone-child-avoiding trees, arXiv:1406.7784 [math.CO], (30-June-2014).

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

Example

The a(1) = 1 through a(5) = 16 trees:
  1  2     3        4           5
     (11)  (111)    (22)        (11111)
           (1(11))  (1111)      ((11)3)
                    (2(11))     (1(22))
                    (1(111))    (2(111))
                    (11(11))    (1(1111))
                    ((11)(11))  (11(111))
                    (1(1(11)))  (111(11))
                                (1(2(11)))
                                (2(1(11)))
                                (1(1(111)))
                                (1(11)(11))
                                (1(11(11)))
                                (11(1(11)))
                                (1((11)(11)))
                                (1(1(1(11))))

Mathematica

disjointQ[u_]:=Apply[And, Outer[#1==#2||Intersection[#1, #2]=={}&, u, u, 1], {0, 1}];
usot[n_]:=Prepend[Join@@Table[Select[Union[Sort/@Tuples[usot/@ptn]], disjointQ[DeleteCases[#, _?AtomQ]]&&SameQ@@Select[#, AtomQ]&], {ptn, Select[IntegerPartitions[n], Length[#]>1&]}], n];
Table[Length[usot[n]], {n, 12}]

Crossrefs

The non-locally disjoint version is A141268.

Locally disjoint trees counted by vertices are A316473.

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

Number of trees counted by A331678 with all atoms equal to 1.

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

Unlabeled lone-child-avoiding locally disjoint rooted trees are A331680.

Cf. A000081, A000669, A001678, A005804, A060356, A300660, A316471, A316694, A316696, A319312, A330465, A331681.

Sequence in context: A292853 A363204 A204516 * A277346 A005648 A113947

Adjacent sequences: A331676 A331677 A331678 * A331680 A331681 A331682

Keyword

nonn,more

Author

Gus Wiseman, Jan 25 2020

Status

approved