A358453 -id:A358453 - cp's OEIS frontend

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

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

A290689 Number of transitive rooted trees with n nodes.

Original entry on oeis.org

1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 88, 143, 229, 370, 592, 955, 1527, 2457, 3929, 6304, 10081

Offset: 1

Gus Wiseman, Oct 19 2017

A rooted tree is transitive if every proper terminal subtree is also a branch of the root. First differs from A206139 at a(13) = 143.

Regarding the notation, a rooted tree is a finite multiset of rooted trees. For example, the rooted tree (o(o)(oo)) is short for {{},{{}},{{},{}}}. Each "o" is a leaf. Each pair of parentheses corresponds to a non-leaf node (such as the root). Its contents "(...)" represent a branch. - Gus Wiseman, Nov 16 2024

			The a(7) = 8 7-node transitive rooted trees are: (o(oooo)), (oo(ooo)), (o(o)((o))), (o(o)(oo)), (ooo(oo)), (oo(o)(o)), (oooo(o)), (oooooo).

Robert P. P. McKone, The transitive rooted trees with n=1 to n=22 nodes.

The restriction to identity trees (A004111) is A279861, ranks A290760.
These trees are ranked by A290822.
The anti-transitive version is A306844, ranks A324758.
The totally transitive case is A318185 (by leaves A318187), ranks A318186.
A version for integer partitions is A324753, for subsets A324736.
The ordered version is A358453, ranks A358457, undirected A358454.
Cf. A000081, A001192, A001678, A324770, A324969, A325705, A358455, A358460.

nn=18;
rtall[n_]:=If[n===1,{{}},Module[{cas},Union[Sort/@Join@@(Tuples[rtall/@#]&/@IntegerPartitions[n-1])]]];
Table[Length[Select[rtall[n],Complement[Union@@#,#]==={}&]],{n,nn}]

a(20) from Robert Price, Sep 13 2018

a(21)-a(22) from Robert P. P. McKone, Dec 16 2023

A358505 Binary encoding of the n-th standard ordered rooted tree.

Original entry on oeis.org

0, 2, 12, 10, 56, 50, 44, 42, 52, 226, 204, 202, 184, 178, 172, 170, 240, 210, 908, 906, 824, 818, 812, 810, 180, 738, 716, 714, 696, 690, 684, 682, 228, 962, 844, 842, 3640, 3634, 3628, 3626, 820, 3298, 3276, 3274, 3256, 3250, 3244, 3242, 752, 722, 2956, 2954

Offset: 1

Gus Wiseman, Nov 20 2022

nonn

The binary encoding of an ordered tree (A014486) is obtained by replacing the internal left and right brackets with 0's and 1's, thus forming a binary number.

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 sixth standard tree is {{{}},{}}, which becomes (1,1,0,0,1,0), so a(6) = 50.

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

Sorting gives A014486.
A dual sequence is A358523.
Cf. A000108, A001263, A057122, A358371, A358372, A358373, A358379, A358453.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
srt[n_]:=If[n==1,{},srt/@stc[n-1]];
trt[t_]:=FromDigits[Take[DeleteCases[Characters[ToString[t]]/.{"{"->1,"}"->0},","|" "],{2,-2}],2];
Table[trt[srt[n]],{n,100}]

A143363 Number of ordered trees with n edges and having no protected vertices. A protected vertex in an ordered tree is a vertex at least 2 edges away from its leaf descendants.

Original entry on oeis.org

1, 1, 1, 3, 6, 17, 43, 123, 343, 1004, 2938, 8791, 26456, 80597, 247091, 763507, 2372334, 7413119, 23271657, 73376140, 232238350, 737638868, 2350318688, 7510620143, 24064672921, 77294975952, 248832007318, 802737926643

Offset: 0

Emeric Deutsch, Aug 20 2008

nonn

The "no protected vertices" condition can be rephrased as "every non-leaf vertex has at least one leaf child". But a(n) is also the number of ordered trees with n edges in which every non-leaf vertex has at most one leaf child. - David Callan, Aug 22 2014
Also the number of locally non-intersecting ordered rooted trees with n edges, meaning every non-leaf subtree has empty intersection. The unordered version is A007562. - Gus Wiseman, Nov 19 2022
a(n) is the number of parking functions of size n-1 avoiding the patterns 123, 132, and 213 . - Lara Pudwell, Apr 10 2023
For n>0, a(n) is the number of ways to place non-intersecting diagonals in convex n+3-gon so as to create no triangles such that none of the dividing diagonals passes through a chosen vertex. (empirical observation) - Muhammed Sefa Saydam, Feb 14 2025 and Aug 05 2025

			From _Gus Wiseman_, Nov 19 2022: (Start)
The a(0) = 1 through a(4) = 6 trees with at least one leaf directly under any non-leaf node:
  o  (o)  (oo)  (ooo)   (oooo)
                ((o)o)  ((o)oo)
                (o(o))  ((oo)o)
                        (o(o)o)
                        (o(oo))
                        (oo(o))
The a(0) = 1 through a(4) = 6 trees with at most one leaf directly under any node:
  o  (o)  ((o))  ((o)o)   (((o))o)
                 (o(o))   (((o)o))
                 (((o)))  ((o)(o))
                          ((o(o)))
                          (o((o)))
                          ((((o))))
(End)

Ayomikun Adeniran and Lara Pudwell, Pattern avoidance in parking functions, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.
Gi-Sang Cheon and Louis W. Shapiro, Protected points in ordered trees, Appl. Math. Letters, 21, 2008, 516-520.
Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016.

Cf. A143362.
For exactly one leaf directly under any node we have A006013.
The unordered version is A007562, ranked by A316470.
Allowing lone children gives A319378.
A000108 counts ordered rooted trees, unordered A000081.
A358453 counts transitive ordered trees, unordered A290689.
A358460 counts locally disjoint ordered trees, unordered A316473.
Cf. A318185, A324756, A324767, A324840, A324844.

p:=z^2*G^3-2*z*G^2-2*z^2*G^2+3*z*G+G+z^2*G-1-2*z=0: G:=RootOf(p,G): Gser:= series(G,z=0,33): seq(coeff(Gser,z,n),n=0..28);

a[n_Integer] := a[n] = Round[SeriesCoefficient[2 (x + 1 - Sqrt[x^2 - x + 1] Cos[ArcTan[(3 x Sqrt[12 x^3 - 96 x^2 - 24 x + 15])/(2 x^3 - 30 x^2 - 3 x + 2)]/3])/(3 x), {x, 0, n}]]; Table[a[n], {n, 0, 20}] (* Vladimir Reshetnikov, Apr 10 2022 *)
RecurrenceTable[{25 (n + 5) (n + 6) a[n + 5] - 10 (n + 5) (5 n + 21) a[n + 4] - 2 (77 n^2 + 613 n + 1185) a[n + 3] + 2 (50 n^2 + 253 n + 312) a[n + 2] + 4 (2 n + 1) (7 n + 9) a[n + 1] - 4 n (2 n + 1) a[n] == 0, a[0] == 1, a[1] == 1, a[2] == 1, a[3] == 3, a[4] == 6}, a[n], {n, 0, 27}] (* Vladimir Reshetnikov, Apr 11 2022 *)
ait[n_]:=ait[n]=If[n==1,{{}},Join@@Table[Select[Tuples[ait/@c],MemberQ[#,{}]&],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[ait[n]],{n,15}] (* Gus Wiseman, Nov 19 2022 *)

a(n) = A143362(n,0) for n>=1.
G.f.: G=G(z) satisfies z^2*G^3-2z(1+z)G^2+(1+3z+z^2)G-(1+2z)=0.
G.f.: (x+1-sqrt(x^2-x+1)*cos(arctan((3*x*sqrt(12*x^3-96*x^2-24*x+15))/(2*x^3-30*x^2-3*x+2))/3))*2/(3*x). - Vladimir Reshetnikov, Apr 10 2022
Recurrence: 25*(n+5)*(n+6)*a(n+5) - 10*(n+5)*(5*n+21)*a(n+4) - 2*(77*n^2+613*n+1185)*a(n+3) + 2*(50*n^2+253*n+312)*a(n+2) + 4*(2*n+1)*(7*n+9)*a(n+1) - 4*n*(2*n+1)*a(n) = 0. - Vladimir Reshetnikov, Apr 11 2022
From Muhammed Sefa Saydam, Jul 12 2025: (Start)
a(n) =  Sum_{k=2..n+2} A046736(k) * A046736(n-k+3) , for n >= 0 and A046736(1) = 1.
a(n) = A049125(n) + Sum_{k=1..n-2} A049125(k) * A046736(n-k+2), for n >= 3.
a(n) = A049125(n) + Sum_{k=1..n-2} a(k) * a(n-k-1), for n >= 3. (End)

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

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Nov 18 2022

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.

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

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.

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

A358454 Number of weakly transitive ordered rooted trees with n nodes.

Original entry on oeis.org

1, 1, 1, 3, 6, 13, 33, 80, 201, 509, 1330, 3432, 8982, 23559, 62189

Offset: 1

Gus Wiseman, Nov 18 2022

We define an unlabeled ordered rooted tree to be weakly transitive if every branch of a branch of the root is itself a branch of the root.

			The a(1) = 1 through a(6) = 13 trees:
  o  (o)  (oo)  (ooo)   (oooo)   (ooooo)
                ((o)o)  ((o)oo)  ((o)ooo)
                (o(o))  ((oo)o)  ((oo)oo)
                        (o(o)o)  ((ooo)o)
                        (o(oo))  (o(o)oo)
                        (oo(o))  (o(oo)o)
                                 (o(ooo))
                                 (oo(o)o)
                                 (oo(oo))
                                 (ooo(o))
                                 ((o)(o)o)
                                 ((o)o(o))
                                 (o(o)(o))

The unordered version is A290689, ranked by A290822.
The directed version is A358453.
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],Complement[Union@@#,#]=={}&]],{n,10}]

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

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Nov 18 2022

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.

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

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.

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

A358524 Binary encoding of balanced ordered rooted trees (counted by A007059).

Original entry on oeis.org

0, 2, 10, 12, 42, 52, 56, 170, 204, 212, 232, 240, 682, 820, 844, 852, 920, 936, 976, 992, 2730, 3276, 3284, 3380, 3404, 3412, 3640, 3688, 3736, 3752, 3888, 3920, 4000, 4032, 10922, 13108, 13132, 13140, 13516, 13524, 13620, 13644, 13652, 14568, 14744, 14760

Offset: 1

Gus Wiseman, Nov 21 2022

nonn

An ordered tree is balanced if all leaves are the same distance from the root.

The binary encoding of an ordered tree (see A014486) is obtained by replacing the internal left and right brackets with 0's and 1's, thus forming a binary number.

			The terms together with their corresponding trees begin:
    0: o
    2: (o)
   10: (oo)
   12: ((o))
   42: (ooo)
   52: ((oo))
   56: (((o)))
  170: (oooo)
  204: ((o)(o))
  212: ((ooo))
  232: (((oo)))
  240: ((((o))))
  682: (ooooo)
  820: ((o)(oo))
  844: ((oo)(o))
  852: ((oooo))
  920: (((o)(o)))
  936: (((ooo)))
  976: ((((oo))))
  992: (((((o)))))

These trees are counted by A007059.
This is a subset of A014486.
The version for binary trees is A057122.
The unordered version is A184155, counted by A048816.
Another ranking of balanced ordered trees is A358459.
A000108 counts ordered rooted trees, unordered A000081.
A358453 counts transitive ordered trees, unordered A290689.
Cf. A001263, A003238, A244925, A358377, A358379, A358523.

binbalQ[n_]:=n==0||Count[IntegerDigits[n,2],0]==Count[IntegerDigits[n,2],1]&&And@@Table[Count[Take[IntegerDigits[n,2],k],0]<=Count[Take[IntegerDigits[n,2],k],1],{k,IntegerLength[n,2]}];
bint[n_]:=If[n==0,{},ToExpression[StringReplace[StringReplace[ToString[IntegerDigits[n,2]/.{1->"{",0->"}"}],","->""],"} {"->"},{"]]]
Select[Range[0,1000],binbalQ[#]&&SameQ@@Length/@Position[bint[#],{}]&]

A358458 Numbers k such that the k-th standard ordered rooted tree is weakly transitive (counted by A358454).

Original entry on oeis.org

1, 2, 4, 6, 7, 8, 12, 14, 15, 16, 18, 22, 23, 24, 25, 27, 28, 30, 31, 32, 36, 38, 39, 42, 44, 45, 46, 47, 48, 50, 51, 53, 54, 55, 56, 57, 59, 60, 62, 63, 64, 70, 71, 72, 76, 78, 79, 82, 84, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 99, 100, 102, 103, 105

Offset: 1

Gus Wiseman, Nov 18 2022

nonn

We define an unlabeled ordered rooted tree to be weakly transitive if every branch of a branch of the root is itself 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)
   6: ((o)o)
   7: (o(o))
   8: (ooo)
  12: ((o)oo)
  14: (o(o)o)
  15: (oo(o))
  16: (oooo)
  18: ((oo)o)
  22: ((o)(o)o)
  23: ((o)o(o))
  24: ((o)ooo)

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

The unordered version is A290822, counted by A290689.
These trees are counted by A358454.
The directed version is A358457, counted by A358453.
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],Complement[Union@@srt[#],srt[#]]=={}&]

A358460 Number of locally disjoint ordered rooted trees with n nodes.

Original entry on oeis.org

1, 1, 2, 5, 13, 36, 103, 301, 902, 2767, 8637, 27324, 87409, 282319, 919352

Offset: 1

Gus Wiseman, Nov 19 2022

Locally disjoint means no branch of any vertex overlaps a different (unequal) branch of the same vertex.

			The a(1) = 1 through a(5) = 13 trees:
  o  (o)  (oo)   (ooo)    (oooo)
          ((o))  ((o)o)   ((o)oo)
                 ((oo))   ((oo)o)
                 (o(o))   ((ooo))
                 (((o)))  (o(o)o)
                          (o(oo))
                          (oo(o))
                          (((o))o)
                          (((o)o))
                          (((oo)))
                          ((o(o)))
                          (o((o)))
                          ((((o))))

The locally non-intersecting version is A143363, unordered A007562.
The unordered version is A316473, ranked by A316495.
A000108 counts ordered rooted trees, unordered A000081.
A358453 counts transitive ordered trees, unordered A290689.
Cf. A006013, A302696, A316471, A316694, A318185, A319378, A324768, A324844.

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A290689 Number of transitive rooted trees with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A358505 Binary encoding of the n-th standard ordered rooted tree.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A143363 Number of ordered trees with n edges and having no protected vertices. A protected vertex in an ordered tree is a vertex at least 2 edges away from its leaf descendants.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A358454 Number of weakly transitive ordered rooted trees with n nodes.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A358524 Binary encoding of balanced ordered rooted trees (counted by A007059).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica