A358453 Number of transitive ordered rooted trees with n nodes.

1, 1, 1, 2, 4, 8, 17, 37, 83, 190, 444, 1051, 2518, 6090, 14852

Offset: 1

Author

Gus Wiseman, Nov 18 2022

Keywords

• nonn
• more

Comments

We define an unlabeled ordered rooted tree to be transitive if every branch of a branch of the root already appears farther to the left as a branch of the root. An undirected version is A358454.

Examples

			The a(1) = 1 through a(7) = 17 trees:
  o  (o)  (oo)  (ooo)   (oooo)   (ooooo)    (oooooo)
                (o(o))  (o(o)o)  (o(o)oo)   (o(o)ooo)
                        (o(oo))  (o(oo)o)   (o(oo)oo)
                        (oo(o))  (o(ooo))   (o(ooo)o)
                                 (oo(o)o)   (o(oooo))
                                 (oo(oo))   (oo(o)oo)
                                 (ooo(o))   (oo(oo)o)
                                 (o(o)(o))  (oo(ooo))
                                            (ooo(o)o)
                                            (ooo(oo))
                                            (oooo(o))
                                            (o(o)(o)o)
                                            (o(o)(oo))
                                            (o(o)o(o))
                                            (o(oo)(o))
                                            (oo(o)(o))
                                            (o(o)((o)))
		

Crossrefs

The unordered version is A290689, ranked by A290822.

The undirected version is A358454, ranked by A358458.

These trees are ranked by A358457.

A000081 counts rooted trees.

A306844 counts anti-transitive rooted trees.

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

Programs

Mathematica

aot[n_]:=If[n==1,{{}},Join@@Table[Tuples[aot/@c],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[Select[aot[n],Function[t,And@@Table[Complement[t[[k]],Take[t,k]]=={},{k,Length[t]}]]]],{n,10}]