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

Author

Gus Wiseman, Jan 31 2020

Keywords

• nonn
• more

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.

Examples

			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)))))
		

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.

Programs

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}]