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

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,3

Comments

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.

Links

Table of n, a(n) for n=1..87.

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

Example

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.

Mathematica

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

Crossrefs

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.

Sequence in context: A265337 A096852 A096857 * A358553 A303639 A090000

Adjacent sequences: A358376 A358377 A358378 * A358380 A358381 A358382

Keyword

nonn

Author

Gus Wiseman, Nov 16 2022

Status

approved