A358373 -id:A358373 - cp's OEIS frontend

A358371 Number of leaves in the n-th standard ordered rooted tree.

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

Offset: 1

Gus Wiseman, Nov 13 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 standard ordered rooted tree ranking begins:
  1: o        10: (((o))o)   19: (((o))(o))
  2: (o)      11: ((o)(o))   20: (((o))oo)
  3: ((o))    12: ((o)oo)    21: ((o)((o)))
  4: (oo)     13: (o((o)))   22: ((o)(o)o)
  5: (((o)))  14: (o(o)o)    23: ((o)o(o))
  6: ((o)o)   15: (oo(o))    24: ((o)ooo)
  7: (o(o))   16: (oooo)     25: (o(oo))
  8: (ooo)    17: ((((o))))  26: (o((o))o)
  9: ((oo))   18: ((oo)o)    27: (o(o)(o))
For example, the 25th ordered tree is (o,(o,o)) because the 24th composition is (1,4) and the 3rd composition is (1,1). Hence a(25) = 3.

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

The triangle counting trees by this statistic is A001263, unordered A055277.
The version for unordered trees is A109129, nodes A061775, edges A196050.
The nodes are counted by A358372.
A000081 counts unordered rooted trees, ranked by A358378.
A000108 counts ordered rooted trees.
A358374 ranks ordered identity trees, counted by A032027.
A358375 ranks ordered binary trees, counted by A126120
Cf. A004249, A005043, A063895, A187306, A284778, A358373, A358376, A358377.

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

A358372 Number of nodes in the n-th standard ordered rooted tree.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Nov 14 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 standard ordered rooted tree ranking begins:
  1: o        10: (((o))o)   19: (((o))(o))
  2: (o)      11: ((o)(o))   20: (((o))oo)
  3: ((o))    12: ((o)oo)    21: ((o)((o)))
  4: (oo)     13: (o((o)))   22: ((o)(o)o)
  5: (((o)))  14: (o(o)o)    23: ((o)o(o))
  6: ((o)o)   15: (oo(o))    24: ((o)ooo)
  7: (o(o))   16: (oooo)     25: (o(oo))
  8: (ooo)    17: ((((o))))  26: (o((o))o)
  9: ((oo))   18: ((oo)o)    27: (o(o)(o))
For example, the 25th ordered tree is (o,(o,o)) because the 24th composition is (1,4) and the 3rd composition is (1,1). Hence a(25) = 5.

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

The triangle counting trees by leaves is A001263, unordered A055277.
The version for unordered trees is A061775, leaves A109129, edges A196050.
The leaves are counted by A358371.
A000081 counts unlabeled rooted trees, ranked by A358378.
A358374 ranks ordered identity trees, counted by A032027.
A358375 ranks ordered binary trees, counted by A126120
Cf. A001678, A004249, A005043, A063895, A284778, A358373, A358376, A358377.

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

A358377 Numbers k such that the k-th standard ordered rooted tree is a generalized Bethe tree (counted by A003238).

Original entry on oeis.org

1, 2, 3, 4, 5, 8, 9, 11, 16, 17, 32, 37, 43, 64, 128, 129, 137, 171, 256, 257, 293, 512, 529, 683, 1024, 1025, 2048, 2185, 2341, 2731, 4096, 8192, 10923, 16384, 16913, 18725, 32768, 32769, 32897, 34953, 43691, 65536, 65537, 131072, 131329, 149797, 174763

Offset: 1

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

A generalized Bethe tree is an unlabeled rooted tree where all branches directly under the same root are equal.

			The terms together with their corresponding ordered rooted 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)
   37: (((o))((o)))
   43: ((o)(o)(o))
   64: (oooooo)
  128: (ooooooo)
  129: ((ooo))
  137: ((oo)(oo))
  171: ((o)(o)(o)(o))

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

These trees are counted by A003238.
The unordered version is A214577, also counted by A003238.
A000081 counts unlabeled rooted trees, ranked by A358378.
A358371 and A358372 count leaves and nodes in standard ordered rooted trees.
A358374 ranks ordered identity trees, counted by A032027.
Cf. A001263, A004111, A004249, A005043, A063895, A276625, A331490, A358373, A358375, A358376.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
srt[n_]:=If[n==1,{},srt/@stc[n-1]];
Select[Range[1000],FreeQ[srt[#],[_]?(!SameQ@@#&)]&]

A358379 Edge-height (or depth) of the n-th standard ordered rooted tree.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Nov 16 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 standard ordered rooted tree ranking begins:
  1: o        10: (((o))o)   19: (((o))(o))
  2: (o)      11: ((o)(o))   20: (((o))oo)
  3: ((o))    12: ((o)oo)    21: ((o)((o)))
  4: (oo)     13: (o((o)))   22: ((o)(o)o)
  5: (((o)))  14: (o(o)o)    23: ((o)o(o))
  6: ((o)o)   15: (oo(o))    24: ((o)ooo)
  7: (o(o))   16: (oooo)     25: (o(oo))
  8: (ooo)    17: ((((o))))  26: (o((o))o)
  9: ((oo))   18: ((oo)o)    27: (o(o)(o))
For example, the 52nd ordered tree is (o((o))oo) so a(52) = 3.

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

Records occur at A004249.
The triangle counting trees by this statistic is A080936, unordered A034781.
Unordered version is A109082, nodes A061775, leaves A109129, edges A196050.
Leaves are counted by A358371.
Nodes are counted by A358372.
Node-height is a(n) + 1, unordered version is A358552.
A000081 counts unordered rooted trees, ranked by A358378.
A000108 counts ordered rooted trees.
A001263 counts ordered rooted trees by leaves.
Cf. A005043, A055277, A187306, A358373, A358374, A358375, A358376, A358377.

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

A358378 Numbers k such that the k-th standard ordered rooted tree is fully canonically ordered (counted by A000081).

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 15, 16, 17, 21, 25, 27, 29, 31, 32, 37, 41, 43, 49, 53, 57, 59, 61, 63, 64, 65, 73, 81, 85, 101, 105, 107, 113, 117, 121, 123, 125, 127, 128, 129, 137, 145, 165, 169, 171, 193, 201, 209, 213, 229, 233, 235, 241, 245, 249, 251

Offset: 1

Gus Wiseman, Nov 14 2022

nonn

The ordering of finitary multisets is first by length and then lexicographically. This is also the ordering used for Mathematica expressions.

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 rooted trees begin:
   1: o
   2: (o)
   3: ((o))
   4: (oo)
   5: (((o)))
   7: (o(o))
   8: (ooo)
   9: ((oo))
  11: ((o)(o))
  13: (o((o)))
  15: (oo(o))
  16: (oooo)
  17: ((((o))))
  21: ((o)((o)))

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

These trees are counted by A000081.
A358371 and A358372 count leaves and nodes in standard ordered rooted trees.
Cf. A001263, A004249, A005043, A032027, A063895, A276625, A358373-A358377.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
srt[n_]:=If[n==1,{},srt/@stc[n-1]];
Select[Range[1000],FreeQ[srt[#],[_]?(!OrderedQ[#]&)]&]

A358579 Numbers k such that the k-th standard ordered rooted tree has the same number of leaves as internal (non-leaf) nodes.

Original entry on oeis.org

2, 6, 7, 9, 20, 22, 23, 26, 27, 29, 35, 41, 66, 76, 78, 79, 84, 86, 87, 90, 91, 93, 97, 102, 103, 106, 107, 109, 115, 117, 130, 136, 138, 139, 141, 146, 153, 163, 169, 193, 196, 197, 201, 226, 241, 262, 263, 296, 300, 302, 303, 308, 310, 311, 314, 315, 317

Offset: 1

Gus Wiseman, Nov 25 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 terms together with their corresponding rooted trees begin:
   2: (o)
   6: (o(o))
   7: ((oo))
   9: ((o)(o))
  20: (oo((o)))
  22: (o(((o))))
  23: (((o)(o)))
  26: (o(o(o)))
  27: ((o)(o)(o))
  29: ((o((o))))
  35: (((o))(oo))
  41: (((o(o))))
  66: (o(o)(((o))))
  76: (oo(ooo))
  78: (o(o)(o(o)))
  79: ((o(((o)))))
  84: (oo(o)(oo))
  86: (o(o(oo)))

These ordered trees are counted by A000891.
The unordered version is A358578, counted by A185650.
Height instead of leaves: counted by A358588, unordered A358576.
Height instead of internals: counted by A358590, unordered A358577.
Standard ordered tree number statistics: A358371, A358372, A358379, A358553.
A000081 counts rooted trees, ordered A000108.
A055277 counts trees by nodes and leaves, ordered A001263.
Cf. A014221, A206487, A358373, A358580, A358587, A358589.

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

A358371(a(n)) = A358553(a(n)).

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

A358376 Numbers k such that the k-th standard ordered rooted tree is lone-child-avoiding (counted by A005043).

Original entry on oeis.org

1, 4, 8, 16, 18, 25, 32, 36, 50, 57, 64, 72, 100, 114, 121, 128, 137, 144, 200, 228, 242, 249, 256, 258, 274, 281, 288, 385, 393, 400, 456, 484, 498, 505, 512, 516, 548, 562, 569, 576, 770, 786, 793, 800, 897, 905, 912, 968, 996, 1010, 1017, 1024, 1032, 1096

Offset: 1

Gus Wiseman, Nov 14 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 initial terms and their corresponding trees:
    1: o
    4: (oo)
    8: (ooo)
   16: (oooo)
   18: ((oo)o)
   25: (o(oo))
   32: (ooooo)
   36: ((oo)oo)
   50: (o(oo)o)
   57: (oo(oo))
   64: (oooooo)
   72: ((oo)ooo)
  100: (o(oo)oo)
  114: (oo(oo)o)
  121: (ooo(oo))
  128: (ooooooo)
  137: ((oo)(oo))
  144: ((oo)oooo)
  200: (o(oo)ooo)

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

These trees are counted by A005043.
The series-reduced case appears to be counted by A284778.
The unordered version is A291636, counted by A001678.
A000081 counts unlabeled rooted trees, ranked by A358378.
A358371 and A358372 count leaves and nodes in standard ordered rooted trees.
A358374 ranks ordered identity trees, counted by A032027.
A358375 ranks ordered binary trees, counted by A126120.
Cf. A000014, A001263, A001679, A004249, A061775, A063895, A187306, A331489, A331490, A331934, A358373, A358377.

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],FreeQ[srt[#],[_]?(Length[#]==1&)]&]

A358374 Numbers k such that the k-th standard ordered rooted tree is an identity tree (counted by A032027).

Original entry on oeis.org

1, 2, 3, 5, 6, 7, 10, 13, 17, 19, 21, 33, 34, 38, 39, 42, 45, 49, 51, 53, 65, 66, 67, 81, 97, 130, 131, 133, 134, 135, 145, 161, 162, 177, 193, 195, 209, 259, 261, 262, 263, 266, 269, 289, 290, 305, 321, 322, 353, 387, 389, 401, 417, 513, 517, 518, 519, 522

Offset: 1

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

A rooted identity tree is an unlabeled rooted tree with no repeated branches directly under the same root.

			The terms together with their corresponding ordered rooted trees begin:
   1: o
   2: (o)
   3: ((o))
   5: (((o)))
   6: ((o)o)
   7: (o(o))
  10: (((o))o)
  13: (o((o)))
  17: ((((o))))
  19: (((o))(o))
  21: ((o)((o)))
  33: (((o)o))
  34: ((((o)))o)
  38: (((o))(o)o)
  39: (((o))o(o))
  42: ((o)((o))o)
  45: ((o)o((o)))

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

These trees are counted by A032027.
The unordered version is A276625, counted by A004111.
A000081 counts unlabeled rooted trees, ranked by A358378.
A358371 and A358372 count leaves and nodes in standard ordered rooted trees.
A358375 ranks ordered binary trees, counted by A126120.
Cf. A001263, A004249, A005043, A063895, A358373, A358376, A358377.

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],FreeQ[srt[#],[_]?(!UnsameQ@@#&)]&]

A358375 Numbers k such that the k-th standard ordered rooted tree is binary.

Original entry on oeis.org

1, 4, 18, 25, 137, 262146, 393217, 2097161, 2228225

Offset: 1

Gus Wiseman, Nov 14 2022

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 initial terms and their corresponding trees:
       1: o
       4: (oo)
      18: ((oo)o)
      25: (o(oo))
     137: ((oo)(oo))
  262146: (((oo)o)o)
  393217: (o((oo)o))

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

The unordered version is A111299, counted by A001190
These trees are counted by A126120.
A000081 counts unlabeled rooted trees, ranked by A358378.
A358371 and A358372 count leaves and nodes in standard ordered rooted trees.
Cf. A001263, A004249, A005043, A063895, A245824, A284778, A358373, A358374, A358376, A358377.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
srt[n_]:=If[n==1,{},srt/@stc[n-1]];
Select[Range[1000],FreeQ[srt[#],[_]?(Length[#]!=2&)]&]

cp's OEIS Frontend

A358371 Number of leaves in the n-th standard ordered rooted tree.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A358372 Number of nodes in the n-th standard ordered rooted tree.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A358377 Numbers k such that the k-th standard ordered rooted tree is a generalized Bethe tree (counted by A003238).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A358379 Edge-height (or depth) of the n-th standard ordered rooted tree.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A358378 Numbers k such that the k-th standard ordered rooted tree is fully canonically ordered (counted by A000081).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A358579 Numbers k such that the k-th standard ordered rooted tree has the same number of leaves as internal (non-leaf) nodes.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A358376 Numbers k such that the k-th standard ordered rooted tree is lone-child-avoiding (counted by A005043).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs