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,3

Comments

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

Links

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

Example

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

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

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.

Sequence in context: A277996 A370168 A099164 * A289453 A339290 A036765

Adjacent sequences: A358457 A358458 A358459 * A358461 A358462 A358463

Keyword

nonn,more

Author

Gus Wiseman, Nov 19 2022

Status

approved