A358458 -id:A358458 - cp's OEIS frontend

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

Gus Wiseman, Nov 18 2022

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.

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

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.

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

A358457 Numbers k such that the k-th standard ordered rooted tree is transitive (counted by A358453).

Original entry on oeis.org

1, 2, 4, 7, 8, 14, 15, 16, 25, 27, 28, 30, 31, 32, 50, 53, 54, 55, 56, 57, 59, 60, 62, 63, 64, 99, 100, 105, 106, 107, 108, 109, 110, 111, 112, 114, 117, 118, 119, 120, 121, 123, 124, 126, 127, 128, 198, 199, 200, 210, 211, 212, 213, 214, 215, 216, 217, 218

Offset: 1

Gus Wiseman, Nov 18 2022

nonn

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.

We define the n-th standard ordered rooted tree to be obtained by taking the (n-1)-th composition in standard order (graded reverse-lexicographic, A066099) as root and replacing each part with its own standard ordered rooted tree. This ranking is an ordered variation of Matula-Goebel numbers, giving a bijective correspondence between positive integers and unlabeled ordered rooted trees.

			The terms together with their corresponding ordered trees begin:
   1: o
   2: (o)
   4: (oo)
   7: (o(o))
   8: (ooo)
  14: (o(o)o)
  15: (oo(o))
  16: (oooo)
  25: (o(oo))
  27: (o(o)(o))
  28: (o(o)oo)
  30: (oo(o)o)
  31: (ooo(o))
  32: (ooooo)
  50: (o(oo)o)
  53: (o(o)((o)))
  54: (o(o)(o)o)
  55: (o(o)o(o))

Gus Wiseman, Statistics, classes, and transformations of standard compositions

The unordered version is A290822, counted by A290689.
These trees are counted by A358453.
The undirected version is A358458, counted by A358454.
A000108 counts ordered rooted trees, unordered A000081.
A306844 counts anti-transitive rooted trees.
A324766 ranks recursively anti-transitive rooted trees, counted by A324765.
A358455 counts recursively anti-transitive ordered rooted trees.
Cf. A004249, A032027, A318185, A324695, A324758, A324766, A324840, A358373-A358377, A358456.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
srt[n_]:=If[n==1,{},srt/@stc[n-1]];
Select[Range[100],Composition[Function[t,And@@Table[Complement[t[[k]],Take[t,k]]=={},{k,Length[t]}]],srt]]

cp's OEIS Frontend

A358453 Number of transitive ordered rooted trees with n nodes.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica