A331783 Number of locally disjoint rooted semi-identity trees with n unlabeled vertices.

1, 1, 2, 4, 8, 17, 37, 83, 191, 450, 1076, 2610, 6404, 15875, 39676, 99880, 253016, 644524, 1649918, 4242226

Offset

1,3

Comments

Locally disjoint means no branch of any vertex overlaps a different (unequal) branch of the same vertex. In a semi-identity tree, all non-leaf branches of any given vertex are distinct.

Links

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

Example

The a(1) = 1 through a(6) = 17 trees:
  o  (o)  (oo)   (ooo)    (oooo)     (ooooo)
          ((o))  ((oo))   ((ooo))    ((oooo))
                 (o(o))   (o(oo))    (o(ooo))
                 (((o)))  (oo(o))    (oo(oo))
                          (((oo)))   (ooo(o))
                          ((o(o)))   (((ooo)))
                          (o((o)))   ((o(oo)))
                          ((((o))))  ((oo(o)))
                                     (o((oo)))
                                     (o(o(o)))
                                     (oo((o)))
                                     ((((oo))))
                                     (((o(o))))
                                     ((o)((o)))
                                     ((o((o))))
                                     (o(((o))))
                                     (((((o)))))

Mathematica

disjunsQ[u_]:=Length[u]==1||UnsameQ@@DeleteCases[u, {}]&&Apply[And, Outer[#1==#2||Intersection[#1, #2]=={}&, u, u, 1], {0, 1}];
ldrsi[n_]:=If[n==1, {{}}, Select[Join@@Function[c, Union[Sort/@Tuples[ldrsi/@c]]]/@IntegerPartitions[n-1], disjunsQ]];
Table[Length[ldrsi[n]], {n, 10}]

Crossrefs

The lone-child-avoiding case is A212804.

The identity tree version is A316471.

The Matula-Goebel numbers of these trees are given by A331682.

Identity trees are A004111.

Semi-identity trees are A306200.

Locally disjoint rooted trees are A316473.

Matula-Goebel numbers of locally disjoint semi-identity trees are A316494.

Cf. A000081, A306202, A316475, A316495, A316694, A331683, A331684, A331686.

Sequence in context: A085022 A324936 A358453 * A003426 A179476 A087803

Adjacent sequences: A331780 A331781 A331782 * A331784 A331785 A331786

Keyword

nonn,more

Author

Gus Wiseman, Jan 31 2020

Status

approved