A358374 -id:A358374 - 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@@#&)]&]

A032027 Number of planted planar trees (n+1 nodes) where any 2 subtrees extending from the same node are different.

Original entry on oeis.org

1, 1, 1, 3, 5, 13, 35, 95, 255, 715, 2081, 6003, 17645, 52127, 155863, 468129, 1415521, 4301055, 13134789, 40275109, 123970669, 382919917, 1186475687, 3686899725, 11487023793, 35876838669, 112304155021, 352276801491

Offset: 1

Christian G. Bower

			From _Gus Wiseman_, Nov 15 2022: (Start)
The a(1) = 1 through a(6) = 13 ordered rooted identity trees (ranked by A358374):
  o  (o)  ((o))  ((o)o)   (((o))o)   (((o)o)o)
                 (o(o))   (((o)o))   ((o(o))o)
                 (((o)))  ((o(o)))   (o((o)o))
                          (o((o)))   (o(o(o)))
                          ((((o))))  ((((o)))o)
                                     ((((o))o))
                                     ((((o)o)))
                                     (((o))(o))
                                     (((o(o))))
                                     ((o)((o)))
                                     ((o((o))))
                                     (o(((o))))
                                     (((((o)))))
(End)

Andrew Howroyd, Table of n, a(n) for n = 1..200
C. G. Bower, Transforms (2)
Index entries for sequences related to rooted trees

The unordered version is A004111, ranked by A276625.
These trees (ordered rooted identity) are ranked by A358374.
Cf. A000081, A001190, A005043, A003238, A063895, A358377.

aot[n_]:=If[n==1,{{}},Join@@Table[Tuples[aot/@c],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[Select[aot[n],FreeQ[#,[_]?(!UnsameQ@@#&)]&]],{n,1,10}] (* Gus Wiseman, Nov 15 2022 *)

AGK(v)={apply(p->subst(serlaplace(y^0*p),y,1), Vec(prod(k=1, #v, (1 + x^k*y + O(x*x^#v))^v[k])-1, -#v))}
seq(n)={my(v=[1]); for(i=2, n, v=concat([1], AGK(v))); v} \\ Andrew Howroyd, Sep 20 2018

Shifts left under "AGK" (ordered, elements, unlabeled) transform.

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

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

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

A032027 Number of planted planar trees (n+1 nodes) where any 2 subtrees extending from the same node are different.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A358379 Edge-height (or depth) 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

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica