A331678 Number of lone-child-avoiding locally disjoint rooted trees whose leaves are integer partitions whose multiset union is an integer partition of n.

1, 3, 6, 18, 44, 149, 450, 1573, 5352, 19283, 69483, 257206

Offset

1,2

Comments

Lone-child-avoiding means there are no unary branchings. Locally disjoint means no child of any vertex has branches overlapping the branches of any other unequal child of the same vertex.

Links

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

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(4) = 18 trees:
  (1)  (2)       (3)            (4)
       (11)      (12)           (13)
       ((1)(1))  (111)          (22)
                 ((1)(2))       (112)
                 ((1)(1)(1))    (1111)
                 ((1)((1)(1)))  ((1)(3))
                                ((2)(2))
                                ((2)(11))
                                ((11)(11))
                                ((1)(1)(2))
                                ((1)((1)(2)))
                                ((2)((1)(1)))
                                ((1)(1)(1)(1))
                                ((11)((1)(1)))
                                ((1)((1)(1)(1)))
                                ((1)(1)((1)(1)))
                                (((1)(1))((1)(1)))
                                ((1)((1)((1)(1))))

Mathematica

sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
disjointQ[u_]:=Apply[And, Outer[#1==#2||Intersection[#1, #2]=={}&, u, u, 1], {0, 1}];
mpti[m_]:=Prepend[Join@@Table[Select[Union[Sort/@Tuples[mpti/@p]], disjointQ], {p, Select[mps[m], Length[#]>1&]}], m];
Table[Sum[Length[mpti[m]], {m, Sort/@IntegerPartitions[n]}], {n, 8}]

Crossrefs

The case where all leaves are singletons is A316696.

The case where all leaves are (1) is A316697.

The non-locally disjoint version is A319312.

The case with all atoms equal to 1 is A331679.

The identity tree case is A331686.

Cf. A000081, A000669, A001678, A005804, A060356, A141268, A196545, A300660, A316471, A316694, A316495, A330465, A331680, A331687.

Sequence in context: A197050 A354387 A121188 * A120718 A032120 A115344

Adjacent sequences: A331675 A331676 A331677 * A331679 A331680 A331681

Keyword

nonn,more

Author

Gus Wiseman, Jan 25 2020

Status

approved