

A085184


Sequence A085183 shown in base 4. Quaternary code for binary trees.


8



0, 1, 2, 11, 12, 21, 22, 30, 111, 112, 121, 122, 130, 211, 212, 221, 222, 230, 301, 302, 310, 320, 1111, 1112, 1121, 1122, 1130, 1211, 1212, 1221, 1222, 1230, 1301, 1302, 1310, 1320, 2111, 2112, 2121, 2122, 2130, 2211, 2212, 2221, 2222, 2230, 2301, 2302
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

This sequence gives two alternative ways to encode rooted plane binary trees (Stanley's interpretation 'c' = interpretation 'd' without the outermost edges):
A: scan each term from left to right and for each 0, add a leaf node to the tree (terminate a branch), for each 1, add a leftward leaning branch \, for each 2, add a rightward leaning branch / and for each 3, add a doublebranch \/ and continue in lefttoright, depthfirst fashion.
B: Like method A, but the roles of digits 1 and 2 are swapped. When one compares the generated trees to the "standard order" as specified in the illustrations for A014486, one obtains the permutation A074684/A074683 for the case A and A082356/A082355 for the case B.
If we assign the following weights for each digit: w(0) = 1, w(1) = w(2) = 0, w(3) = +1, then the sequence gives all base4 numbers for which all the partial sums of digit weights (from the most significant to the least significant end) are nonnegative and the final sum is zero. The initial term 0 is considered to have no significant digits at all, so its total weight is zero also.


LINKS

Table of n, a(n) for n=1..48.
R. P. Stanley, Exercises on Catalan and Related Numbers


FORMULA

a(n) = A007090(A085183(n))


EXAMPLE

For the first eleven terms the following binary trees are constructed with method A. With method B we would get their mirror images, although this doesn't hold in general (e.g. for terms like 301320).
........................................................\......./......\...
.....................\......./.......\......./...........\......\....../...
..*......\....../.....\......\......./....../.....\/......\......\.....\...
..0......1......2.....11.....12.....21.....22.....30....111....112....121..


CROSSREFS

Cf. A085185. Number of terms with n significant digits is given by A000108(n+1).
Sequence in context: A136986 A096109 A136997 * A037089 A038118 A038117
Adjacent sequences: A085181 A085182 A085183 * A085185 A085186 A085187


KEYWORD

nonn,base


AUTHOR

Antti Karttunen Jun 14 2003


STATUS

approved



