A358523 - OEIS

%I #6 Nov 21 2022 09:38:25

%S 1,2,4,3,8,7,6,9,5,16,15,14,25,13,12,11,18,129,65,10,33,257,17,32,31,

%T 30,57,29,28,27,50,385,193,26,97,769,49,24,23,22,41,21,36,35,258,

%U 32769,16385,130,8193,16777217,4097,20,19,66

%N Standard ordered tree numbers of ordered trees in order of their binary encodings (A014486).

%C 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.

%C 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.

%H 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 The first six binary encodings are: 0, 2, 10, 12, 42, 44, and the corresponding trees have standard ranks: 1, 2, 4, 3, 8, 7.

%t stcinv[q_]:=Total[2^Accumulate[Reverse[q]]]/2;

%t srtinv[t_]:=If[t=={},1,stcinv[srtinv/@t]+1];

%t binbalQ[n_]:=n==0||Count[IntegerDigits[n,2],0]==Count[IntegerDigits[n,2],1]&&And@@Table[Count[Take[IntegerDigits[n,2],k],0]<=Count[Take[IntegerDigits[n,2],k],1],{k,IntegerLength[n,2]}];

%t bint[n_]:=If[n==0,{},ToExpression[StringReplace[StringReplace[ToString[IntegerDigits[n,2]/.{1->"{",0->"}"}],","->""],"} {"->"},{"]]]

%t Table[srtinv[bint[n]],{n,Select[Range[0,100],binbalQ]}]

%Y A dual sequence is A358505.

%Y A000108 counts ordered rooted trees, unordered A000081.

%Y A014486 lists all binary encodings.

%Y Cf. A001263, A014221, A057122, A358371, A358372, A358373, A358379.

%K nonn

%O 0,2

%A _Gus Wiseman_, Nov 21 2022