|
|
A358523
|
|
Standard ordered tree numbers of ordered trees in order of their binary encodings (A014486).
|
|
5
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
A014486 lists all binary encodings.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|