The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #9 Mar 28 2014 23:38:27
%S 0,10,1010,1100,101100,101010,110010,110100,10110100,10110010,
%T 10101010,10101100,11001100,11001010,11010010,111000,10111000,
%U 1011010010,1011001010,1011001100,1010101100,1010101010,1010110010,1010110100
%N 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.
%H A. Karttunen, <a href="http://www.iki.fi/~kartturi/matikka/Nekomorphisms/ACO1.htm">Alternative Catalan Orderings</a> (with the complete Scheme source)
%e The rooted plane trees encoded here are:
%e .....................o........o.........o......o...o...
%e .....................|........|.........|.......\./....
%e .......o....o...o....o....o...o..o.o.o..o...o....o.....
%e .......|.....\./.....|.....\./....\|/....\./.....|.....
%e (AT)......(AT)......(AT)......(AT)......(AT)......(AT)......(AT)......(AT).....
%e 0......1......2......3......4......5......6......7.....
%e 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.
%o (Scheme functions showing the essential idea. For the complete source, follow the "Alternative Catalan Orderings" link:)
%o (define (A075171 n) (A007088 (parenthesization->binexp (binruns->parenthesization n))))
%o (define (binruns->parenthesization n) (map binruns->parenthesization (map -1+ (binexp->runcount1list n))))
%o (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)))))))
%Y 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.
%K nonn,base
%O 0,2
%A _Antti Karttunen_, Sep 13 2002