login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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 A163662

Adjacent sequences:  A075168 A075169 A075170 * A075172 A075173 A075174

KEYWORD

nonn,base

AUTHOR

Antti Karttunen, Sep 13 2002

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 23 20:42 EDT 2021. Contains 347617 sequences. (Running on oeis4.)