1,3

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 double-branch \/, and continue in left-to-right, depth-first 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 base-4 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.

R. P. Stanley, Exercises on Catalan and Related Numbers

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

For the eleven first terms the following binary trees are constructed with method A. With method B we would get their mirror images, although it doesn't hold in general (e.g. for terms like 301-320).

........................................................\......./......\...

.....................\......./.......\......./...........\......\....../...

..*......\....../.....\......\......./....../.....\/......\......\.....\...

..0......1......2.....11.....12.....21.....22.....30....111....112....121..

Cf. A085185. Number of terms with n significant digits is given by A000108(n+1).

Adjacent sequences: A085181 A085182 A085183 this_sequence A085185 A085186 A085187

Sequence in context: A136986 A096109 A136997 this_sequence A037089 A038118 A038117

nonn,base

Antti Karttunen (my_firstname.my_surname(AT)iki.fi) Jun 14 2003