cp's OEIS Frontend

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

%I A358372 #5 Nov 14 2022 15:38:01
%S A358372 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,
%T A358372 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,
%U A358372 7,7,7,7,7,8,8,8,8,8,8,8,7,7,8,8,8,8,8
%N A358372 Number of nodes in the n-th standard ordered rooted tree.
%C A358372 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 A358372 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 A358372 The standard ordered rooted tree ranking begins:
%e A358372   1: o        10: (((o))o)   19: (((o))(o))
%e A358372   2: (o)      11: ((o)(o))   20: (((o))oo)
%e A358372   3: ((o))    12: ((o)oo)    21: ((o)((o)))
%e A358372   4: (oo)     13: (o((o)))   22: ((o)(o)o)
%e A358372   5: (((o)))  14: (o(o)o)    23: ((o)o(o))
%e A358372   6: ((o)o)   15: (oo(o))    24: ((o)ooo)
%e A358372   7: (o(o))   16: (oooo)     25: (o(oo))
%e A358372   8: (ooo)    17: ((((o))))  26: (o((o))o)
%e A358372   9: ((oo))   18: ((oo)o)    27: (o(o)(o))
%e A358372 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.
%t A358372 stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
%t A358372 srt[n_]:=If[n==1,{},srt/@stc[n-1]];
%t A358372 Table[Count[srt[n],_,{0,Infinity}],{n,100}]
%Y A358372 The triangle counting trees by leaves is A001263, unordered A055277.
%Y A358372 The version for unordered trees is A061775, leaves A109129, edges A196050.
%Y A358372 The leaves are counted by A358371.
%Y A358372 A000081 counts unlabeled rooted trees, ranked by A358378.
%Y A358372 A358374 ranks ordered identity trees, counted by A032027.
%Y A358372 A358375 ranks ordered binary trees, counted by A126120
%Y A358372 Cf. A001678, A004249, A005043, A063895, A284778, A358373, A358376, A358377.
%K A358372 nonn
%O A358372 1,2
%A A358372 _Gus Wiseman_, Nov 14 2022