A358456 Number of recursively bi-anti-transitive ordered rooted trees with n nodes.

1, 1, 2, 3, 7, 17, 47, 117, 321, 895, 2556, 7331, 21435, 63116, 187530

Offset

1,3

Comments

We define an unlabeled ordered rooted tree to be recursively bi-anti-transitive if there are no two branches of the same node such that one is a branch of the other.

Links

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

Example

The a(1) = 1 through a(6) = 17 trees:
  o  (o)  (oo)   (ooo)    (oooo)     (ooooo)
          ((o))  ((oo))   ((ooo))    ((oooo))
                 (((o)))  (((o))o)   (((o))oo)
                          (((oo)))   (((oo))o)
                          ((o)(o))   (((ooo)))
                          (o((o)))   ((o)(oo))
                          ((((o))))  ((oo)(o))
                                     (o((o))o)
                                     (o((oo)))
                                     (oo((o)))
                                     ((((o)))o)
                                     ((((o))o))
                                     ((((oo))))
                                     (((o)(o)))
                                     ((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_, ___}, ___}|{___, {___, x_, ___}, ___, x_, ___}]&]], {n, 10}]

Crossrefs

The unordered version is A324765, ranked by A324766.

The directed version is A358455.

A000108 counts ordered rooted trees, unordered A000081.

A306844 counts anti-transitive rooted trees.

A358453 counts transitive ordered trees, unordered A290689.

Cf. A318185, A324695, A324751, A324756, A324758, A324764, A324767, A324768, A324838, A324840, A324844.

Sequence in context: A113483 A173868 A274291 * A208987 A176074 A281368

Adjacent sequences: A358453 A358454 A358455 * A358457 A358458 A358459

Keyword

nonn,more

Author

Gus Wiseman, Nov 18 2022

Status

approved