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,2

Links

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

A. Karttunen, Alternative Catalan Orderings (with the complete Scheme source)

Example

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.

Prog

(Scheme functions showing the essential idea. For the complete source, follow the "Alternative Catalan Orderings" link:)
(define (A075171 n) (A007088 (parenthesization->binexp (binruns->parenthesization n))))
(define (binruns->parenthesization n) (map binruns->parenthesization (map -1+ (binexp->runcount1list n))))
(define (binexp->runcount1list n) (if (zero? n) (list) (let loop ((n n) (rc (list)) (count 0) (prev-bit (modulo n 2))) (if (zero? n) (cons count rc) (if (eq? (modulo n 2) prev-bit) (loop (floor->exact (/ n 2)) rc (1+ count) (modulo n 2)) (loop (floor->exact (/ n 2)) (cons count rc) 1 (modulo n 2)))))))

Crossrefs

Permutation of A063171. Same sequence shown in decimal: A075170. The digital length of each term / 2 (the number of o-nodes in the corresponding trees) is given by A075172. Cf. A075166, A007088.

Sequence in context: A063171 A075166 A071671 * A106456 A079214 A377192

Adjacent sequences: A075168 A075169 A075170 * A075172 A075173 A075174

Keyword

nonn,base

Author

Antti Karttunen, Sep 13 2002

Status

approved