A075171 Nonnegative integers mapped to Dyck path encodings of the rooted plane trees obtained by recursing on the run lengths of the binary expansion of n.
0, 10, 1010, 1100, 101100, 101010, 110010, 110100, 10110100, 10110010, 10101010, 10101100, 11001100, 11001010, 11010010, 111000, 10111000, 1011010010, 1011001010, 1011001100, 1010101100, 1010101010, 1010110010, 1010110100
Offset: 0
Examples
The rooted plane trees encoded here are: .....................o........o.........o......o...o... .....................|........|.........|.......\./.... .......o....o...o....o....o...o..o.o.o..o...o....o..... .......|.....\./.....|.....\./....\|/....\./.....|..... (AT)......(AT)......(AT)......(AT)......(AT)......(AT)......(AT)......(AT)..... 0......1......2......3......4......5......6......7..... Note that we recurse on the run length - 1, thus for 4 = 100 in binary, we construct a tree by joining trees 0 (= 1-1) and 1 (= 2-1) respectively from left to right. For 5 (101) we construct a tree by joining three copies of tree 0 (a single leaf) with a new root node. For 6 (110) we join trees 1 and 0 to get a mirror image of tree 4. For 7 (111) we just add a new root node below tree 2.
Links
- A. Karttunen, Alternative Catalan Orderings (with the complete Scheme source)