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

1, 2, 4, 8, 17, 41, 103, 280, 793, 2330, 6979, 21291

Offset

1,2

Comments

A rooted tree is locally disjoint if no child of any vertex has branches overlapping the branches of any other (unequal) child of the same vertex. Lone-child-avoiding means there are no unary branchings. In an identity tree, all branches of any given vertex are distinct.

Links

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

Example

The a(1) = 1 through a(5) = 17 trees:
  (1)  (2)   (3)       (4)            (5)
       (11)  (12)      (13)           (14)
             (111)     (22)           (23)
             ((1)(2))  (112)          (113)
                       (1111)         (122)
                       ((1)(3))       (1112)
                       ((2)(11))      (11111)
                       ((1)((1)(2)))  ((1)(4))
                                      ((2)(3))
                                      ((1)(22))
                                      ((3)(11))
                                      ((2)(111))
                                      ((1)((1)(3)))
                                      ((2)((1)(2)))
                                      ((11)((1)(2)))
                                      ((1)((2)(11)))
                                      ((1)((1)((1)(2))))

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]], UnsameQ@@#&&disjointQ[#]&], {p, Select[mps[m], Length[#]>1&]}], m];
Table[Sum[Length[mpti[m]], {m, Sort/@IntegerPartitions[n]}], {n, 8}]

Crossrefs

The non-identity version is A331678.

The case where the leaves are all singletons is A316694.

Identity trees are A004111.

Locally disjoint identity trees are A316471.

Locally disjoint enriched identity p-trees are A331684.

Lone-child-avoiding locally disjoint rooted semi-identity trees are A212804.

Cf. A000669, A001678, A005804, A141268, A300660, A316697, A319312, A331679, A331683, A331783, A331874, A331875.

Sequence in context: A307555 A104879 A366220 * A156805 A200542 A272105

Adjacent sequences: A331683 A331684 A331685 * A331687 A331688 A331689

Keyword

nonn,more

Author

Gus Wiseman, Jan 31 2020

Status

approved