A358455 - OEIS

%I #7 Nov 18 2022 21:53:03

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

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

%C 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.

%e The a(1) = 1 through a(5) = 10 trees:

%e   o  (o)  (oo)   (ooo)    (oooo)

%e           ((o))  ((o)o)   ((o)oo)

%e                  ((oo))   ((oo)o)

%e                  (((o)))  ((ooo))

%e                           (((o))o)

%e                           (((o)o))

%e                           (((oo)))

%e                           ((o)(o))

%e                           (o((o)))

%e                           ((((o))))

%t aot[n_]:=If[n==1,{{}},Join@@Table[Tuples[aot/@c],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];

%t Table[Length[Select[aot[n],FreeQ[#,{___,x_,___,{___,x_,___},___}]&]],{n,10}]

%Y The unordered version is A324765, ranked by A324766.

%Y The undirected version is A358456.

%Y A000108 counts ordered rooted trees, unordered A000081.

%Y A306844 counts anti-transitive rooted trees.

%Y A358453 counts transitive ordered trees, unordered A290689.

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

%K nonn,more

%O 1,3

%A _Gus Wiseman_, Nov 18 2022