A358460 Number of locally disjoint ordered rooted trees with n nodes.

1, 1, 2, 5, 13, 36, 103, 301, 902, 2767, 8637, 27324, 87409, 282319, 919352

Offset: 1

Author

Gus Wiseman, Nov 19 2022

Keywords

• nonn
• more

Comments

Locally disjoint means no branch of any vertex overlaps a different (unequal) branch of the same vertex.

Examples

			The a(1) = 1 through a(5) = 13 trees:
  o  (o)  (oo)   (ooo)    (oooo)
          ((o))  ((o)o)   ((o)oo)
                 ((oo))   ((oo)o)
                 (o(o))   ((ooo))
                 (((o)))  (o(o)o)
                          (o(oo))
                          (oo(o))
                          (((o))o)
                          (((o)o))
                          (((oo)))
                          ((o(o)))
                          (o((o)))
                          ((((o))))
		

Crossrefs

The locally non-intersecting version is A143363, unordered A007562.

The unordered version is A316473, ranked by A316495.

A000108 counts ordered rooted trees, unordered A000081.

A358453 counts transitive ordered trees, unordered A290689.

Cf. A006013, A302696, A316471, A316694, A318185, A319378, A324768, A324844.

Programs

Mathematica

aot[n_]:=If[n==1,{{}},Join @@ Table[Tuples[aot/@c],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[Select[aot[n],FreeQ[#,{_,{_,x_,_},_,{_,x_,_},_}]&]],{n,10}]