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

1, 1, 2, 4, 10, 26, 72, 206, 608, 1830, 5612, 17442, 54866, 174252, 558072, 1800098

Offset

1,3

Comments

We define an unlabeled ordered rooted tree to be recursively anti-transitive if no branch of a branch of a subtree is a branch of the same subtree farther to the left.

Links

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

Example

The a(1) = 1 through a(5) = 10 trees:
  o  (o)  (oo)   (ooo)    (oooo)
          ((o))  ((o)o)   ((o)oo)
                 ((oo))   ((oo)o)
                 (((o)))  ((ooo))
                          (((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 unordered version is A324765, ranked by A324766.

The undirected version is A358456.

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: A154835 A049145 A102407 * A356832 A148097 A148098

Adjacent sequences: A358452 A358453 A358454 * A358456 A358457 A358458

Keyword

nonn,more

Author

Gus Wiseman, Nov 18 2022

Status

approved