cp's OEIS Frontend

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

%I A358379 #11 Nov 27 2022 10:33:45
%S A358379 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,
%T A358379 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,
%U A358379 3,2,2,2,3,3,3,3,3,3,3,3,4,2,3,3,3,2,2
%N A358379 Edge-height (or depth) of the n-th standard ordered rooted tree.
%C A358379 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.
%H A358379 Gus Wiseman, <a href="https://docs.google.com/document/d/e/2PACX-1vTCPiJVFUXN8IqfLlCXkgP15yrGWeRhFS4ozST5oA4Bl2PYS-XTA3sGsAEXvwW-B0ealpD8qnoxFqN3/pub">Statistics, classes, and transformations of standard compositions</a>
%e A358379 The standard ordered rooted tree ranking begins:
%e A358379   1: o        10: (((o))o)   19: (((o))(o))
%e A358379   2: (o)      11: ((o)(o))   20: (((o))oo)
%e A358379   3: ((o))    12: ((o)oo)    21: ((o)((o)))
%e A358379   4: (oo)     13: (o((o)))   22: ((o)(o)o)
%e A358379   5: (((o)))  14: (o(o)o)    23: ((o)o(o))
%e A358379   6: ((o)o)   15: (oo(o))    24: ((o)ooo)
%e A358379   7: (o(o))   16: (oooo)     25: (o(oo))
%e A358379   8: (ooo)    17: ((((o))))  26: (o((o))o)
%e A358379   9: ((oo))   18: ((oo)o)    27: (o(o)(o))
%e A358379 For example, the 52nd ordered tree is (o((o))oo) so a(52) = 3.
%t A358379 stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
%t A358379 srt[n_]:=If[n==1,{},srt/@stc[n-1]];
%t A358379 Table[Depth[srt[n]]-2,{n,100}]
%Y A358379 Records occur at A004249.
%Y A358379 The triangle counting trees by this statistic is A080936, unordered A034781.
%Y A358379 Unordered version is A109082, nodes A061775, leaves A109129, edges A196050.
%Y A358379 Leaves are counted by A358371.
%Y A358379 Nodes are counted by A358372.
%Y A358379 Node-height is a(n) + 1, unordered version is A358552.
%Y A358379 A000081 counts unordered rooted trees, ranked by A358378.
%Y A358379 A000108 counts ordered rooted trees.
%Y A358379 A001263 counts ordered rooted trees by leaves.
%Y A358379 Cf. A005043, A055277, A187306, A358373, A358374, A358375, A358376, A358377.
%K A358379 nonn
%O A358379 1,3
%A A358379 _Gus Wiseman_, Nov 16 2022