A358373 -id:A358373 - cp's OEIS frontend

A358523 Standard ordered tree numbers of ordered trees in order of their binary encodings (A014486).

1, 2, 4, 3, 8, 7, 6, 9, 5, 16, 15, 14, 25, 13, 12, 11, 18, 129, 65, 10, 33, 257, 17, 32, 31, 30, 57, 29, 28, 27, 50, 385, 193, 26, 97, 769, 49, 24, 23, 22, 41, 21, 36, 35, 258, 32769, 16385, 130, 8193, 16777217, 4097, 20, 19, 66

Offset: 0

Gus Wiseman, Nov 21 2022

nonn

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

			The first six binary encodings are: 0, 2, 10, 12, 42, 44, and the corresponding trees have standard ranks: 1, 2, 4, 3, 8, 7.

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

A dual sequence is A358505.
A000108 counts ordered rooted trees, unordered A000081.
A014486 lists all binary encodings.
Cf. A001263, A014221, A057122, A358371, A358372, A358373, A358379.

stcinv[q_]:=Total[2^Accumulate[Reverse[q]]]/2;
srtinv[t_]:=If[t=={},1,stcinv[srtinv/@t]+1];
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->"}"}],","->""],"} {"->"},{"]]]
Table[srtinv[bint[n]],{n,Select[Range[0,100],binbalQ]}]

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

A358553 Number of internal (non-leaf) nodes in the n-th standard ordered rooted tree.

Original entry on oeis.org

0, 1, 2, 1, 3, 2, 2, 1, 2, 3, 3, 2, 3, 2, 2, 1, 4, 2, 4, 3, 4, 3, 3, 2, 2, 3, 3, 2, 3, 2, 2, 1, 3, 4, 3, 2, 5, 4, 4, 3, 3, 4, 4, 3, 4, 3, 3, 2, 4, 2, 4, 3, 4, 3, 3, 2, 2, 3, 3, 2, 3, 2, 2, 1, 3, 3, 5, 4, 4, 3, 3, 2, 4, 5, 5, 4, 5, 4, 4, 3, 5, 3, 5, 4, 5, 4, 4

Offset: 1

Gus Wiseman, Nov 26 2022

nonn

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 89-th standard rooted tree is ((o)o(oo)), and it has 3 internal nodes, so a(89) = 3.

This statistic is counted by A001263, unordered A358575 (reverse A055277).
The unordered version is A342507, firsts A358554.
Other statistics: A358371 (leaves), A358372 (nodes), A358379 (edge-height).
A000081 counts rooted trees, ordered A000108.
Cf. A000891, A014221, A358373, A358585, A358586, A358588.

stc[n_]:=Reverse[Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]];
srt[n_]:=If[n==1,{},srt/@stc[n-1]];
Table[Count[srt[n],[_],{0,Infinity}],{n,100}]

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[#]]=={}&]

A358550 Depth of the ordered rooted tree with binary encoding A014486(n).

Original entry on oeis.org

1, 2, 2, 3, 2, 3, 3, 3, 4, 2, 3, 3, 3, 4, 3, 3, 3, 3, 4, 4, 4, 4, 5, 2, 3, 3, 3, 4, 3, 3, 3, 3, 4, 4, 4, 4, 5, 3, 3, 3, 3, 4, 3, 3, 3, 3, 4, 4, 4, 4, 5, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 2, 3, 3, 3, 4, 3, 3, 3, 3, 4, 4, 4, 4, 5, 3, 3, 3, 3, 4, 3, 3, 3

Offset: 1

Gus Wiseman, Nov 22 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.

			The first few rooted trees in binary encoding are:
    0: o
    2: (o)
   10: (oo)
   12: ((o))
   42: (ooo)
   44: (o(o))
   50: ((o)o)
   52: ((oo))
   56: (((o)))
  170: (oooo)
  172: (oo(o))
  178: (o(o)o)
  180: (o(oo))
  184: (o((o)))

Positions of first appearances are A014137.
Leaves of the ordered tree are counted by A057514, standard A358371.
Branches of the ordered tree are counted by A057515.
Edges of the ordered tree are counted by A072643.
The Matula-Goebel number of the ordered tree is A127301.
Positions of 2's are A155587, indices of A020988.
The standard ranking of the ordered tree is A358523.
Nodes of the ordered tree are counted by A358551, standard A358372.
For standard instead of binary encoding we have A358379.
A000108 counts ordered rooted trees, unordered A000081.
A014486 lists all binary encodings.
Cf. A001263, A057122, A358373, A358505, A358524.

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->"}"}],","->""],"} {"->"},{"]]];
Table[Depth[bint[k]]-1,{k,Select[Range[0,1000],binbalQ]}]

A358551 Number of nodes in the ordered rooted tree with binary encoding A014486(n).

Original entry on oeis.org

1, 2, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7

Offset: 1

Gus Wiseman, Nov 22 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.

			The first few rooted trees in binary encoding are:
    0: o
    2: (o)
   10: (oo)
   12: ((o))
   42: (ooo)
   44: (o(o))
   50: ((o)o)
   52: ((oo))
   56: (((o)))
  170: (oooo)
  172: (oo(o))
  178: (o(o)o)
  180: (o(oo))
  184: (o((o)))

Run-lengths are A000108.
Binary encodings are listed by A014486.
Leaves of the ordered tree are counted by A057514, standard A358371.
Branches of the ordered tree are counted by A057515.
Edges of the ordered tree are counted by A072643.
The Matula-Goebel number of the ordered tree is A127301.
For standard instead of binary encoding we have A358372.
The standard ranking of the ordered tree is A358523.
Depth of the ordered tree is A358550, standard A358379.
Cf. A000081, A001263, A057122, A358373, A358505, A358524.

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->"}"}],","->""],"} {"->"},{"]]];
Table[Count[bint[k],_,{0,Infinity}],{k,Select[Range[0,10000],binbalQ]}]

a(n) = A072643(n) + 1.

A358459 Numbers k such that the k-th standard ordered rooted tree is balanced (counted by A007059).

Original entry on oeis.org

1, 2, 3, 4, 5, 8, 9, 11, 16, 17, 32, 35, 37, 41, 43, 64, 128, 129, 137, 139, 163, 169, 171, 256, 257, 293, 512, 515, 529, 547, 553, 555, 641, 649, 651, 675, 681, 683, 1024, 1025, 2048, 2053, 2057, 2059, 2177, 2185, 2187, 2211, 2217, 2219, 2305, 2341, 2563

Offset: 1

Gus Wiseman, Nov 19 2022

nonn

An ordered tree is balanced if all leaves have the same distance from 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)
   3: ((o))
   4: (oo)
   5: (((o)))
   8: (ooo)
   9: ((oo))
  11: ((o)(o))
  16: (oooo)
  17: ((((o))))
  32: (ooooo)
  35: ((oo)(o))
  37: (((o))((o)))
  41: ((o)(oo))
  43: ((o)(o)(o))

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

These trees are counted by A007059.
The unordered version is A184155, counted by A048816.
A000108 counts ordered rooted trees, unordered A000081.
A358379 gives depth of standard ordered trees.
Cf. A003238, A004249, A032027, A244925, A290822, A318185, A358373-A358378.

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],SameQ@@Length/@Position[srt[#],{}]&]

cp's OEIS Frontend

A358523 Standard ordered tree numbers of ordered trees in order of their binary encodings (A014486).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

A358553 Number of internal (non-leaf) nodes in the n-th standard ordered rooted tree.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A358550 Depth of the ordered rooted tree with binary encoding A014486(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A358551 Number of nodes in the ordered rooted tree with binary encoding A014486(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A358459 Numbers k such that the k-th standard ordered rooted tree is balanced (counted by A007059).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica