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

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, 30, 57, 29, 28, 27, 50, 385, 193, 26, 97, 769, 49, 24, 23, 22, 41, 21, 36, 35, 258, 32769, 16385, 130, 8193, 16777217, 4097, 20, 19, 66

Offset

0,2

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.

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.

Links

Table of n, a(n) for n=0..53.

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

Example

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.

Mathematica

stcinv[q_]:=Total[2^Accumulate[Reverse[q]]]/2;
srtinv[t_]:=If[t=={}, 1, stcinv[srtinv/@t]+1];
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]}];
bint[n_]:=If[n==0, {}, ToExpression[StringReplace[StringReplace[ToString[IntegerDigits[n, 2]/.{1->"{", 0->"}"}], ", "->""], "} {"->"}, {"]]]
Table[srtinv[bint[n]], {n, Select[Range[0, 100], binbalQ]}]

Crossrefs

A dual sequence is A358505.

A000108 counts ordered rooted trees, unordered A000081.

A014486 lists all binary encodings.

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

Sequence in context: A166133 A237739 A337909 * A365930 A111699 A067179

Adjacent sequences: A358520 A358521 A358522 * A358524 A358525 A358526

Keyword

nonn

Author

Gus Wiseman, Nov 21 2022

Status

approved