|
| |
|
|
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.
|
|
6
|
|
|
|
0, 10, 1010, 1100, 101100, 101010, 110010, 110100, 10110100, 10110010, 10101010, 10101100, 11001100, 11001010, 11010010, 111000, 10111000, 1011010010, 1011001010, 1011001100, 1010101100, 1010101010, 1010110010, 1010110100
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
LINKS
|
|
|
|
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.
|
|
|
KEYWORD
|
nonn,base
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
